NOIP17提高模拟训练18 长途旅行(travel)

题目描述:

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+2d] 也是等于true 的,其中d表示为一条与i相连接的边的长度.
稍加推导可以得知,我们从0到n-1 的路上可以有很多个环,所以我们会经过一条与0相连的边好几次,我们可以反复地经过这条边,如果这条边的长度为p,就有f[i][j] = f[i][j%(2p)] (即自己通过这条边到自己).

结合最短路

图论里减少走的次数的最好办法就是最短路，要把两者结合起来，发现从0点出来的一条边来回走可以形成一个2w的自环，于是用2w进行压缩，记录到每个点的距离，在mod2w的情况下的最小值，这样比这个值大的都可以看成是走过几次环之后的结果，这样就可以舍掉不要了，最后看dist[n-1][n%2w],如果结果不大于T，都可以用上几个2w填补，如果超了或者干脆到不了，就不行
既然是取余，肯定要选择最小的出边，这样状态也更少，时间上也优

Code

#include<bits/stdc++.h>
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<tail){
        int u = d[++head], tt = ti[head];
        for (int w = listt[u]; w ; w = next[w]){
            int v = toit[w];
            if (dis[n][tl%p]<=tl){ printf("Possible
"); return;}
            if (dis[v][(tt+len[w])%p]>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
"); else printf("Impossible
");
}
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;
}

---