路径 ssl 2651 spfa+暴力

题目大意

给出一个n个点m条边的无向图，每条边的长度均为1，要求回答k个询问，每次询问给出(s,t,d)，问是否存在一条从s到t的路径，长度为d，若有满足的路径，则输出TAK，否则输出NIE。每个点每条边允许经过多次。

分析

如果s到t有长度为d的路径 那么就一定有长度为d+2的路径 因此只要spfa求出s开始到每个点的奇数长度的最短路和偶数长度的最短路（分层图）。 然后和D比较大小。 特判自己连自己的情况。

code

#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<string> #include<algorithm> #include<stack> #include<queue> using namespace std; struct arr{ int x,y,w,next; }edge[50000]; int ls[10000]; int dis[5002][5002][2]; int v[5002][2]; int n,m,k,s,t; int edge_m; void add(int x,int y,int w) { edge_m++; edge[edge_m]=(arr){x,y,w,ls[x]};ls[x]=edge_m; edge_m++; edge[edge_m]=(arr){y,x,w,ls[y]};ls[y]=edge_m; } void spfa() { for (int i=1;i<=n;i++) dis[s][i][1]=2000000000,dis[s][i][0]=2000000000; memset(v,0,sizeof(v)); queue<int> q; queue<int> qq; dis[s][s][0]=0; qq.push(0); q.push(s); v[s][0]=1; do{ int x=q.front(); int xx=qq.front(); for (int i=ls[x];i;i=edge[i].next) if (dis[s][edge[i].y][xx^1]>dis[s][x][xx]+edge[i].w) { dis[s][edge[i].y][xx^1]=dis[s][x][xx]+edge[i].w; if (!v[edge[i].y][xx^1]) { v[edge[i].y][xx^1]=1; q.push(edge[i].y); qq.push(xx^1); } } v[x][xx]=0; q.pop(); qq.pop(); }while (!q.empty()); } int vv[10000]; int vvv[10000]; int main() { freopen("way.in", "r", stdin); freopen("way.out", "w", stdout); scanf("%d%d%d",&n,&m,&k); for (int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); vvv[x]=1; vvv[y]=1; if (x==y) vv[x]=1; add(x,y,1); } for (int i=1;i<=n;i++) { s=i; spfa(); } for (int i=1;i<=k;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); s=x; t=y; if (x==y) { if (z%2) if (dis[s][t][1]<=z) printf("TAK\n"); else printf("NIE\n"); else if (vvv[x]) printf("TAK\n"); else printf("NIE\n"); continue; } if (z%2) if (dis[s][t][1]<=z) printf("TAK\n"); else printf("NIE\n"); else if (dis[s][t][0]<=z) printf("TAK\n"); else printf("NIE\n"); } fclose(stdin); fclose(stdout); }