题目描述:
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
数据范围:
30%: T <= 10000
另有30%: n <= 5 , m <= 10 , Case <= 5. 100%: 2 <= n <= 50, 1 <= m <= 100, 1 <= z <= 10000, 1 <= T <= 10^18, Case <= 15.
时间限制:
1S
空间限制:
256M
solution
一个简单的想法:
我们先假设F[I,J]为花费时间为J能否到达T ,设len[i]为第i条路的长度,这条路所连接的两个点分别为u[i]和v[i].
显然,有 *F[0][0] = true , f[v[i],j] = f[v[i],j] or f[u[i],j-len[i](2p+1)]* (因为一条路可以走多次) 然而这明显是TLE了,而且10^18 也不允许我们开那么大的数组
一个奇妙的发现:
因为每条路可以走N次,那么我们可以发现,如果f[i][j] = true ,f[i][j+2*d] 也是等于true 的,其中d表示为一条与i相连接的边的长度.
稍加推导可以得知,我们从0到n-1 的路上可以有很多个环,所以我们会经过一条与0相连的边好几次,我们可以反复地经过这条边,如果这条边的长度为p,就有f[i][j] = f[i][j%(2*p)] (即自己通过这条边到自己).
结合最短路
图论里减少走的次数的最好办法就是最短路,要把两者结合起来,发现从0点出来的一条边来回走可以形成一个2w的自环,于是用2w进行压缩,记录到每个点的距离,在mod2w的情况下的最小值,这样比这个值大的都可以看成是走过几次环之后的结果,这样就可以舍掉不要了,最后看dist[n-1][n%2w],如果结果不大于T,都可以用上几个2w填补,如果超了或者干脆到不了,就不行
既然是取余,肯定要选择最小的出边,这样状态也更少,时间上也优
Code
#includeusing namespace std;const int maxn = 205;int tot,listt[maxn],p,d[5000000],ti[5000000],toit[maxn],len[maxn],next[maxn],n,m;long long tl,dis[maxn][20005];inline void add(int u,int v,int w){ toit[++tot] = v; len[tot] = w; next[tot] = listt[u]; listt[u] = tot; if (u==1) p = 2*w;}inline void spfa(){ for (int i=1; i<=n; ++i) for (int j=0; j<=p; ++j) dis[i][j] = 1000000000000000009; int head = 0, tail = 1; dis[1][0] = 0; ti[1] = 0; d[1] = 1; while (head dis[u][tt]+len[w]){ dis[v][(tt+len[w])%p] = dis[u][tt] + len[w]; d[++tail] = v; ti[tail] = (tt+len[w])% p; } } } if (dis[n][tl%p]<=tl) printf("Possible\n"); else printf("Impossible\n");}int main(){ int T; scanf("%d",&T); while (T--){ memset(listt,0,sizeof(listt)); tot = 0; scanf("%d%d%lld",&n,&m,&tl); for (int i=1; i<=m; ++i){ int x,y,z; scanf("%d%d%d",&x,&y,&z); x += 1 ; y += 1; add(x,y,z); add(y,x,z); } spfa(); } return 0;}