SDUT 2622 - 最短路徑（SPFA+二維）

2019-11-08 18:48:34

字體：大中小

來源：轉載

供稿：網友

題目鏈接

http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/PRoblemdetail/pid/2622.html

題目大意

有一個有向圖，給定一個終點和起點，求起點到終點的最短路徑，并且路徑經過的邊數是 x 的倍數。

解題過程

想了好長時間，最初是想把每次的步數一起裝到隊列里面，用 SPFA 。然后 WA ，只好去搜了下博客，原來是多了個維度，和之前做的一個題神似，UVA1600 ，這個是多了一個維度的BFS，以后得想起來這個加一個維度解決問題的方法了，要不遇到就卡死。

題目分析

大體思路是用 SPFA ，增加一個維度，儲存步數對 x 取模，最后輸出對 x 取模后是 0 的終點距離即可。

AC代碼

#include<bits/stdc++.h>using namespace std;struct node{ int v; long long w; node(int v, long long w):v(v),w(w){}};vector<node> edges[112];bool book[112];long long dis[112][11];int s, e, x;int n, m;int main(){ int T; scanf("%d", &T); while (T--) { scanf("%d %d", &n, &m); memset(book, 0, sizeof(book)); memset(dis, -1, sizeof(dis)); for (int i = 0; i < n; i++) edges[i].clear(); for (int i = 0; i < m; i++) { int u, v; long long w; scanf("%d %d %lld", &u, &v, &w); edges[u].push_back(node(v,w)); } scanf("%d %d %d", &s, &e, &x); queue<int> q; q.push(s); dis[s][0] = 0; while (!q.empty()) { int u = q.front(); for (int i = 0; i < edges[u].size(); i++) { int v = edges[u][i].v; long long w = edges[u][i].w; for (int k = 0; k < x; k++) { if (dis[u][k] != -1 && (dis[v][(k+1)%x] > dis[u][k] + w || dis[v][(k+1)%x] == -1)) { dis[v][(k+1)%x] = dis[u][k] + w; if (!book[v]) { q.push(v); book[v] = 1; } } } } book[u] = 0; q.pop(); } if (dis[e][0] == -1) printf("No Answer!/n"); else printf("%lld/n", dis[e][0]); }}

上一篇：引用類型之Function類型

下一篇：STL中的set&&map