[TIOJ 1530] 皮皮歷險記--魔尊皮皮

這題其實我懷疑測資有問題QQ，一直WA兩筆測資，但我證出我的作法不會錯，另外顏睿楠也寫了一樣的作法也WA了QQ

作法：

感覺題目寫的有點難懂......總之我對題目的理解是：求某個起點到某個終點的最短路，但每次經過的邊的 p 值都要嚴格遞增。

如果直接套最短路的作法，會發現每個點的狀態會多一維「上一次是用 p 值多少的邊走過來的」，但這樣會爛掉，時間和記憶體都不夠。如果考慮把邊們按照 p 值從小到大加進圖中，考慮新加入的一條邊，設他的兩端點是 x , y ，那麼如果從起點到某個點的最短路因此而變短了，那麼這個點一定是 x 或 y 。因為如果新得最短路不經過新加入的這條邊，那麼根本不會變短，而如果有經過，那這條邊一定是最後一個走的，因為每次經過的邊的 p 值都要嚴格遞增，新加進來的這條邊是目前圖裡面 p 值最大的邊，不可能走完這條邊之後再去走其他的邊。

最後只要好好的處理如果有很多條邊的 p 值相同的情形，其實就是把他們一次都鬆弛完再一次更新最短路長，因為不能連續走兩條 p 值一樣的邊。

以下是沒有AC的code QQ。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=2000000+10 ;
 
struct P
{
    int from,to ; LL t,p ;
    bool operator < (const P &rhs) const
    {
        return p==rhs.p ? t<rhs.t : p<rhs.p ;
    }
};
 
vector<P> edge ;
LL d[maxn] ;
int id[maxn] ;
LL val[maxn] ;
main()
{
    int n,m,st,ed ;
    scanf("%d%d%d%d",&n,&m,&st,&ed) ;
    memset(d,-1,sizeof(d)) ; d[st]=0 ;
    while(m--)
    {
        int x,y ; LL t,p ; scanf("%d%d%lld%lld",&x,&y,&t,&p) ;
        edge.push_back((P){x,y,t,p}) ;
    }
    sort(edge.begin(),edge.end()) ;
    for(int i=0;i<edge.size();i++)
    {
        int j ;
        for(j=i;j<edge.size() && edge[j].p==edge[i].p;j++) ; j-- ;
        int cnt=0 ;
        for(int k=i;k<=j;k++)
        {
            int x=edge[k].from , y=edge[k].to ;
            LL t=edge[k].t ;
            if(d[y]!=-1 && (d[x]==-1 || d[x]>d[y]+t))
                id[cnt]=x , val[cnt]=d[y]+t , cnt++ ;
            if(d[x]!=-1 && (d[y]==-1 || d[y]>d[x]+t))
                id[cnt]=y , val[cnt]=d[x]+t , cnt++ ;
        }
        for(int k=0;k<cnt;k++)
            d[id[k]]= d[id[k]]==-1 ? val[k] : min(d[id[k]],val[k]) ;
        i=j ;
    }
    if(d[ed]==-1) printf("Pipi how way!!!\n") ;
    else printf("%lld\n",d[ed]) ;
}