题目描述
JY是一个爱旅游的探险家，也是一名强迫症患者。现在JY想要在C国进行一次长途旅行，C国拥有n个城市(编号为0,1,2...,n - 1)，城市之间有m条道路，可能某个城市到自己有一条道路，也有可能两个城市之间有多条道路，通过每条道路都要花费一些时间。JY从0号城市开始出发，目的地为n – 1号城市。由于JY想要好好参观一下C国，所以JY想要旅行恰好T小时。为了让自己的旅行更有意思，JY决定不在任何一个时刻停留(走一条到城市自己的路并不算停留)。JY想知道是否能够花恰好T小时到达n
– 1号城市（每个城市可经过多次）。现在这个问题交给了你。
若可以恰好到达输出“Possible”否则输出“Impossible”。(不含引号)。
输入格式
第一行一个正整数Case，表示数据组数。
每组数据第一行3个整数，分别为n, m, T。
接下来m行，每行3个整数x, y, z,代表城市x和城市y之间有一条耗时为z的双向边。
输出格式
对于每组数据输出”Possible”或者”Impossible”.
样例输入
2
3 3 11
0 2 7
0 1 6
1 2 5
2 1 10000
1 0 1
样例输出
Possible
Impossible
样例解释
第一组：0 -> 1 -> 2 :11
第二组：显然偶数时间都是不可能的。
数据范围
30%: T <= 10000
另有30%: n <= 5 , m <= 10.
100%: 2 <= n <= 50 , 1 <= m <= 100 , 1 <= z <= 10000 , 1 <= T <= 10^18 , Case <= 5.
题解
最近看起来做了不少神神叨叨的最短路。感觉这道题的解题思路非常的奇怪。不看正解还想不到……下面是题解的讲法：
当T<= 10000的时候，可以设 vis[i][j] 代表到达第i个点时间为j是否合法。 这样是O(T*m)，应该可以拿到小数据，就没打了。
当T很大的时候，我们考虑如果0 -> x -> n - 1路径时间为T，且 从x出发有一个时间为d的环，则 一定存在一个K满足 K + p*d = T（至少T满足条件），这样我们就能绕着环走p次就能构成一条时间为T的路径。
显然要求的路径一定经过 0，而且在合法情况下从0号点出发一定存在一条边，否则0号点和n - 1号就是不联通的。随便取一条边时间为d, 则能构成从0号点出发的一个时间为2d的环。这样原题就化为最短路问题了，dis[i][j] 代表到达i号点，时间为 j + p * 2d，最小的 j+p*2d。最后判断dis[n -1][T % 2d] 是否小于等于T即可。实际上就是在30%的基础上缩减状态。时间复杂度为O(m*d)。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define ll long long
#define MOD 1000002
using namespace std;
int C,n,m,zz,head[52],mod;
ll T,dis[52][20002];
struct bian{int to,nx,v;} e[202];
int q[10000002][2];
void insert(int x,int y,int z)
{
zz++; e[zz].to=y; e[zz].v=z; e[zz].nx=head[x]; head[x]=zz;
zz++; e[zz].to=x; e[zz].v=z; e[zz].nx=head[y]; head[y]=zz;
if(x==0||y==0) mod=2*z;
}
void init()
{
memset(head,0,sizeof(head));
zz=0; mod=-1;
scanf("%d%d%I64d",&n,&m,&T);
int i,x,y,z;
for(i=1;i<=m;i++)
{scanf("%d%d%d",&x,&y,&z);
insert(x,y,z);
}
}
void spfa()
{
int i,t=0,w=1,x,p,y,d;
memset(dis,127,sizeof(dis));
q[0][0]=0; q[0][1]=0; dis[0][0]=0;
while(t!=w)
{x=q[t][0]; y=q[t][1]; t=(t+1)%MOD;
//t++;
for(i=head[x];i;i=e[i].nx)
{p=e[i].to;
d=(e[i].v+y)%mod;
if(dis[p][d]>dis[x][y]+e[i].v)
{dis[p][d]=dis[x][y]+e[i].v;
q[w][0]=p; q[w][1]=d;
w=(w+1)%MOD;
//w++;
}
}
}
if(dis[n-1][T%mod]<=T) puts("Possible");
else puts("Impossible");
}
int main()
{
freopen("travel.in","r",stdin);
freopen("travel.out","w",stdout);
scanf("%d",&C);
while(C--)
{init();
if(mod==-1) {puts("Impossible"); continue;}
spfa();
}
return 0;
}