题目描述:

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

#include
    
     using 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;}
     
    

---