時間限制：1 秒

內存限制：32 兆

特殊判題：否

提交：8064

解決：2685

題目描述：

給你n個點，m條無向邊，每條邊都有長度d和花費p，給你起點s終點t，要求輸出起點到終點的最短距離及其花費，如果最短距離有多條路線，則輸出花費最少的。

輸入：

輸入n,m，點的編號是1~n,然后是m行，每行4個數 a,b,d,p，表示a和b之間有一條邊，且其長度為d，花費為p。最后一行是兩個數 s,t;起點s，終點t。n和m為0時輸入結束。
(1<n<=1000, 0<m<100000, s != t)

輸出：

輸出 一行有兩個數， 最短距離及其花費。

樣例輸入：

3 2 1 2 5 6 2 3 4 5 1 3 0 0

樣例輸出：

9 11

來源：

2010年浙江大學計算機及軟件工程研究生機試真題

思路：

典型最短路徑問題，通常有兩種方法：Dijkstra和floyd算法。我比較喜歡用前一種。

最短路徑算法的介紹可參見博客：http://blog.csdn.net/damenhanter/article/details/24771913

本題除了最短路徑，還加上了花費，其實原理一樣的。

代碼：

#include <stdio.h>#define N 1000 #define INF 1000000000int D[N][N], P[N][N]; int visit[N], dis[N], pay[N];void init(int n) {for (int i=0; i<n; i++){visit[i] = 0;for (int j=0; j<n; j++){D[i][j] = INF;P[i][j] = INF;}} }void printdis(int n) {int i;for (i=0; i<n-1; i++)printf("%d ", dis[i]);printf("%d\n", dis[i]); }void dijkstra(int s, int n) {int i, j;for (i=0; i<n; i++){dis[i] = D[s][i];pay[i] = P[s][i];}dis[s] = 0;pay[s] = 0;visit[s] = 1;//printdis(n);int mind, minp;int k;for (i=0; i<n; i++){mind = INF;minp = INF;for (j=0; j<n; j++){if ( !visit[j] && (dis[j]<mind|| dis[j]==mind && pay[j]<minp) ){mind = dis[j];minp = pay[j];k = j;}}visit[k] = 1;for (j=0; j<n; j++){if ( !visit[j] && (dis[k]+D[k][j] < dis[j]|| dis[k]+D[k][j] == dis[j] && pay[k]+P[k][j] < pay[j]) ){dis[j] = dis[k]+D[k][j];pay[j] = pay[k]+P[k][j];}}}//printdis(n); }int main(void) {int n, m, i;int a, b, d, p;int s, t;while (scanf("%d%d", &n, &m) != EOF){if (n == 0 && m == 0)break;init(n);for(i=0; i<m; i++){scanf("%d%d%d%d", &a, &b, &d, &p);D[a-1][b-1] = D[b-1][a-1] = d;P[a-1][b-1] = P[b-1][a-1] = p;}scanf("%d%d", &s, &t);dijkstra(s-1, n);printf("%d %d\n", dis[t-1], pay[t-1]);} return 0; } /**************************************************************Problem: 1008User: liangrx06Language: CResult: AcceptedTime:20 msMemory:8736 kb ****************************************************************/

轉載于:https://www.cnblogs.com/liangrx06/p/5084023.html

總結

以上是生活随笔為你收集整理的九度OJ 1008：最短路径问题 （最短路）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。