題意：

每個(gè)農(nóng)場有一頭牛，現(xiàn)在要到農(nóng)場x開派對，路徑是單向的，要求開完派對后還要回到原農(nóng)場，求所有牛的最短路徑的最大值

要點(diǎn)：

就是一個(gè)定終點(diǎn)求最短路徑的變形，現(xiàn)在已經(jīng)知道終點(diǎn)，從終點(diǎn)回到原農(nóng)場的最短路徑很好求，直接dijkstra算法即可，想求原農(nóng)場到終點(diǎn)的最短路徑只要將所有的單向路反向即可。利用函數(shù)的參量傳遞可以比較方便的求出。

15382144

Seasonal

3268

Accepted

8056K

47MS

C++

1136B

2016-04-12 14:32:55

#include<stdio.h> #include<stdlib.h> #include<string.h> #define INF 0x3f3f3f3f int n, m, start; int map[1005][1005], mapt[1005][1005]; int d1[1005], d2[1005]; bool vis[1005];void dijkstra(int x,int mapx[][1005],int dis[])//利用參量傳遞 {memset(vis, true, sizeof(vis));for (int i = 1; i <= n; i++)dis[i] = mapx[x][i];vis[x] = false;int min, temp;for (int i = 1; i <= n; i++){min = INF;for (int j = 1; j <= n;j++)if (vis[j] && min > dis[j]){temp = j;min = dis[j];}vis[temp] = false;for (int j = 1; j <= n; j++)if (vis[j] && dis[temp] + mapx[temp][j] < dis[j])dis[j] = dis[temp] + mapx[temp][j];} }int main() {scanf("%d%d%d", &n, &m, &start);for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++){if (i == j)map[i][j] = mapt[i][j] = 0;elsemap[i][j] = mapt[i][j] = INF;//開兩個(gè)路徑記錄數(shù)組，節(jié)省了時(shí)間}while (m--){int a, b, t;scanf("%d%d%d", &a, &b, &t);map[a][b] = t;mapt[b][a] = t;}dijkstra(start, map,d1);dijkstra(start, mapt, d2);int max = -1;for (int i = 1; i <= n; i++){if (max < d1[i]+d2[i])max = d1[i]+d2[i];}printf("%d\n", max);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/seasonal/p/10343783.html

總結(jié)

以上是生活随笔為你收集整理的POJ3268 Silver Cow Party(最短路径)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。