「NOIP模拟赛」长途旅行
「题目描述」
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.
题解
对于30%的数据
f[i][j]表示到i的路径长为j是否存在路径，然后直接spfa
考虑起点的某条出边，长度为d
则若1到n存在路径长度为D，且D+2kd=T
则possible
所以f[i][j]表示到i，j+2kd的最短路，最后判断f[n][T mod 2d]是否小于T
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #include<map> #define pa pair<int,int> #define inf 1000000000 #define ll long long using namespace std; 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-'0';ch=getchar();} return x*f; } ll T; int n,m,cas,cnt,last[55],mod; int q1[10000005],q2[10000005]; ll dis[55][20005]; struct data{int to,next,v;}e[205]; void insert(int u,int v,int w) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w; if(u==1||v==1)mod=2*w; } bool spfa() { memset(dis,127/3,sizeof(dis)); int head=0,tail=1; dis[1][0]=0; q1[0]=1;q2[0]=0; while(head!=tail) { int now=q1[head],t=q2[head];head++; for(int i=last[now];i;i=e[i].next) { int to=(e[i].v+t)%mod; if(dis[e[i].to][to]>dis[now][t]+e[i].v) { dis[e[i].to][to]=e[i].v+dis[now][t]; q1[tail]=e[i].to; q2[tail]=to; tail++; } } } if(dis[n][T%mod]<=T)return 1; return 0; } int main() { //freopen("travel.in","r",stdin); //freopen("travel.out","w",stdout); cas=read(); while(cas--) { mod=-1; memset(last,0,sizeof(last)); cnt=0; n=read();m=read();T=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(),w=read(); u++;v++; insert(u,v,w); } if(mod==-1)puts("Impossible"); else if(spfa())puts("Possible"); else puts("Impossible"); } return 0; } |
OI 课件=>
黄学长，请问为什么任取一条起点的出边就行？难道不可以答案的方案是在某条1到n的路径上的结点对（i，j）（i,j != 1）之间的边走k次，其他的只走一次吗？
因为这题的T很大，所以要对路径长度进行分类，我们发现，任取一条长为d的出边，模2d意义下的路径长度都是合法的。
至于这些路径走不走环无所谓，但是处理后能保证你在某个环上绕的次数不超过2d，这样保证复杂度
黄学长，问一下为什么任取一个环判断就可以了啊。能证明吗？
（Ps.我猜黄学长肯定不记得我是谁了）
说点什么…