本文共 1898 字，大约阅读时间需要 6 分钟。

题意

一个国家有N个城市，这些城市被标为0,1,2,…N-1。这些城市间连有M条道路，每条道路连接两个不同的城市，且道路都是双向的。一个小鹿喜欢在城市间沿着道路自由的穿梭，初始时小鹿在城市0处，它最终的目的地是城市N-1处。小鹿每在一个城市，它会选择一条道路，并沿着这条路一直走到另一个城市，然后再重复上述过程。每条道路会花费小鹿不同的时间走完，在城市中小鹿不花时间逗留。路程中，小鹿可以经过一条路多次也可以经过一个城市多次。给定城市间道路的信息，问小鹿是否有一种走法，从城市0出发到达城市N-1时，恰好一共花费T个单位的时间。如果存在输出“Possible”，否则输出“Impossible”。

第一行三个整数，N，M，T，且2<=N<=50,1<=M<=50，1<=T<=1,000,000,000,000,000,000(即 $10^{18}$). 之后M行，每行三个整数Ai,Bi,Di,表示城市Ai与Bi间有一条双向道路，且小鹿穿越这条路要花费Di的时间。其中，0<=Ai,Bi

题解

这题一开始看到，n，m很小，T很大

就往倍增floyd想 然后发现，$t/2$秒怎么都合并不成$t$秒 然后想到他肯定是有若干个环组成的 于是想去找环。。但是我发现我无法找出所有的环。。 然后注意到时双向边，也就是一条边可以走来走去当做一个环 然后，然后，有什么用啊！！！ 于是就GG了。。跑去看题解 题解很妙啊，但是我也有自己的理解，所以有了改动。 但是51nod上面还是AC了，如果有人要hac我，可以在评论指出 其实不需要枚举所有的边，只需要任意枚举一条w可以连向终点的边就可以了然后这条边仅仅只是说可以吧他当做环，但不一定要，也就是可以不用如果他不用的话，也就是有路径自己可以到达t，那么这条路径%(2*w)还是等于t%(2*w)不影响正确性，数据都过了，等被人hack 时间复杂度，（如果把SPFA看成dij的话）$N*E*log(N*E)$ AC CODE:

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;typedef long long LL;#define PI pair
        
         const LL N=55;LL T;LL n,m,t;struct qq{ LL x,y,z,last;}e[N*2];LL num,last[N];void init (LL x,LL y,LL z){ num++; e[num].x=x;e[num].y=y;e[num].z=z; e[num].last=last[x]; last[x]=num;}LL w;LL f[20005][N];void SPFA (){ memset(f,127,sizeof(f)); queue
         
           q; f[0][1]=0;q.push(make_pair(0,1)); while (!q.empty()) { LL z=q.front().first,x=q.front().second;q.pop(); for (LL u=last[x];u!=-1;u=e[u].last) { LL y=e[u].y,zz=(z+e[u].z)%w; if (f[zz][y]>f[z][x]+e[u].z) { f[zz][y]=f[z][x]+e[u].z; q.push(make_pair(zz,y)); } } }}int main(){ scanf("%lld",&T); while (T--) { num=0;memset(last,-1,sizeof(last)); scanf("%lld%lld%lld",&n,&m,&t); for (LL u=1;u<=m;u++) { LL x,y,z; scanf("%lld%lld%lld",&x,&y,&z); x++;y++; init(x,y,z);init(y,x,z); } bool ok=false; w=e[last[n]].z*2; SPFA(); if (f[t%w][n]<=t) ok=true; if (ok==false) printf("Impossible\n"); else printf("Possible\n"); } return 0;}