题目链接。
题目:
最短路径
题目描述
为了准备一年一度的校赛,大家都在忙着往赛场搬运东西,比如气球什么的。这时 YY 也没有闲着,他也加入了搬运工的行列。已知学校有 N 个路口和 M 条路,YY 并不是把东西直接搬到赛场,而是从 S 路口搬运到 T 路口。由于 YY 非常懒而且他有轻度强迫症。所以他要走的路需要尽可能的短,并且走过路径的数目要为 X 的倍数。
输入
输入的第一行为一个正整数T(1 ≤ T ≤ 20),代表测试数据组数。
对于每组测试数据:
输入的第一行为两个正整数 N 和 M(1 ≤ N ≤ 100, 1 ≤ M ≤ 10000)。
接下来M行每行三个正整数 U、V、W(0 ≤ U, V < N, 0 ≤ W ≤ 230 ),代表有一条从U到V的长度为W的有向路径。
最后一行为三个正整数S、T 、X(0 ≤ S, T < N, 1 ≤ X ≤ 10)。
输出
对于每组测试数据,输出满足条件的从 S 到 T 的最短路径。如果从 S 到 T 不可达,或者无法满足路径数是 X 的倍数,输出“No Answer!”(不包含引号)。
注意:64-bit 整型请使用 long long 来定义,并且使用 %lld 或 cin、cout 来输入输出,请不要使用 __int64 和 %I64d。
示例输入
2 2 1 0 1 1 0 1 2 3 2 0 1 1 1 2 1 0 2 2
示例输出
No Answer! 2
分析:
对于每个点,都存在 x 种情况, 即对 x 取余 余0(即整除)、 余2、 余3、...、余x-1。例如对于1点,有d[1][0], d[1][1], d[1][2]....
每走一步要在原来的路径数上加1。
关于最短路的求法就和原来一样。
#include <iostream> #include <cstdlib> #include <cstdio> #include <algorithm> #include <cstring> #include <stack> #include <vector> #include <queue> using namespace std; const long long maxn = 102; struct edge{ int v; long long w; }; long long d[maxn][11]; int n, m, x; bool vis[maxn]; vector<edge> G[maxn]; void spfa(int v0){ memset(d, -1, sizeof(d)); memset(vis, false, sizeof(vis)); queue<int> q; q.push(v0); d[v0][0] = 0; vis[v0] = true; while(!q.empty()){ int u = q.front(); q.pop(); vis[u] = false; for(int i=0; i<G[u].size(); i++){ int v = G[u][i].v; long long w = G[u][i].w; for(int i=0; i<x; i++) if(d[u][i] != -1){ if(d[v][(i+1)%x] == -1 || d[u][i] + w < d[v][(i+1)%x]){ d[v][(i+1)%x] = d[u][i] + w; if(!vis[v]){ q.push(v); vis[v] = true; } } } } } } int main(){ int T, s, t; cin>>T; while(T--){ cin>>n>>m; for(int i=0; i<n; i++) G[i].clear(); for(int i=0; i<m; i++){ int u, v; long long w; cin>>u>>v>>w; edge e; e.v = v; e.w = w; G[u].push_back(e); } cin>>s>>t>>x; spfa(s); if(d[t][0] == -1) printf("No Answer!\n"); else cout<<d[t][0]<<endl; } return 0; }