首页 > 代码库 > 潍坊一中模拟赛10.25 长途旅行
潍坊一中模拟赛10.25 长途旅行
【题目描述】
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.
一张有重边和自环的无向图，一个人从0点出发，走到n-1处停止，一个城市可以反复走多次，每走一条边花费一定时间，是否能正好花费时间T
一看到能否，就知道是一种判定问题，主要矛盾在于，如果这么跑的话，会出现一个城市反复跑很多次，才能累加到T的情况，而累加到T，T<=10^18，时间上不允许，所以要压缩，而压缩最好的办法就是取余，在图论里减少走的次数的最好办法就是最短路，要把两者结合起来，发现从0点出来的一条边来回走可以形成一个2w的自环，于是用2w进行压缩，记录到每个点的距离，在mod2w的情况下的最小值，这样比这个值大的都可以看成是走过几次环之后的结果，这样就可以舍掉不要了，最后看dist[n-1][n%2w],如果结果不大于T，都可以用上几个2w填补，如果超了或者干脆到不了，就不行
既然是取余，肯定要选择最小的出边，这样状态也更少，时间上也优
#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<algorithm>#include<queue>#include<vector>#include<stack>#include<map>#define inf 987654321#define ll long longusing namespace std;char ch;ll t,n,m,md;struct edge{ int v; int w;};struct dat{ int d; int u;};vector<edge> g[55];bool vis[55][10005];ll dist[55][10005];inline int read(){ int x = 0,f = 1; char ch = getchar(); while(ch<‘0‘ || ch>‘9‘){ if(ch==‘-‘)f=-1; ch = getchar(); } while(ch>=‘0‘&&ch<=‘9‘){ x = x*10+ch-48; ch = getchar(); } return x*f;}inline ll Read(){ ll x = 0,f = 1; char ch = getchar(); while(ch<‘0‘ || ch>‘9‘){ if(ch==‘-‘)f=-1; ch = getchar(); } while(ch>=‘0‘&&ch<=‘9‘){ x = x*10+ch-48; ch = getchar(); } return x*f;}void spfa(){ memset(dist,63,sizeof(dist)); memset(vis,false,sizeof(vis)); dist[0][0] = 0; dat tmp; tmp.u = tmp.d = 0; queue<dat> q; q.push(tmp); while(!q.empty()){ tmp = q.front(); q.pop(); int u = tmp.u,d = tmp.d,dd,to; vis[u][d] = false; for(int j = 0;j < g[u].size();j++){ to = g[u][j].v; dd = g[u][j].w + d; int nmod = dd%md; if(dist[to][nmod] > dd){ dist[to][nmod] = dd; if(!vis[to][nmod]){ vis[to][nmod] = true; tmp.d = nmod; tmp.u = to; q.push(tmp); } } } }}int main(){ freopen("travel.in","r",stdin); freopen("travel.out","w",stdout); int T = read(); edge tmp; while(T--){ n = read(); m = read(); t = Read(); md = inf; for(int i = 1;i <= m;i++){ int u=read(),v=read(),w=read(); tmp.v = v; tmp.w = w; g[u].push_back(tmp); tmp.v = u; g[v].push_back(tmp); if(md > w && (!u||!v)) md = w; } md*=2; spfa(); if(dist[n-1][t%md] <= t) cout<<"Possible"<<endl; else cout<<"Impossible"<<endl; for(int i = 0;i <= n;i++) g[i].clear(); } return 0;}
潍坊一中模拟赛10.25 长途旅行