- 題目描述:
- 給你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
該題與 九度OJ題目1447:最短路 使用相同思想,隻是多了一個cost變量
九度OJ題目1447:最短路 我的解法:http://blog.csdn.net/qq_31820885/article/details/61925864
#include <stdio.h>
#include<vector>
using namespace std;
struct E{
int next;
int weight;
int cost;
};
vector<E> edge[1001];
bool mark[1001];
int dis[1001];
int costs[1001];
int main()
{
int n,m;
while(scanf("%d%d", &n,&m)!=EOF) {
if(n == 0 && m == 0) break;
for(int i=1;i<=n;i++) edge[i].clear(); //初始化
int p1,p2,weight,cost;
//錄入
while(m--) {
scanf("%d%d%d%d",&p1,&p2,&weight,&cost);
E tmp;
tmp.weight = weight;
tmp.cost = cost;
tmp.next = p1;
edge[p2].push_back(tmp); //p2與p1的連線放到p2的vector中
tmp.next = p2;
edge[p1].push_back(tmp); //該圖是無向圖,所有要兩個節點的vector都要存彼此
}
int s,t;
scanf("%d%d", &s,&t);
//初始化
for(int i=1;i<=n;i++) {
mark[i] = false;
dis[i] = -1;
// costs[i] = 0;
}
//從s節點為初始K集合
mark[s] = true;
dis[s] = 0;
int newP = s; //新加入K集合的節點
//循環找到特定節點到其他n-1個節點的最短路徑
for(int i=1;i<n;i++) {
for(int j=0;j<edge[newP].size();j++) {
int next = edge[newP][j].next; //新加入節點的相鄰節點
int weight = edge[newP][j].weight;
int cost = edge[newP][j].cost;
if(mark[next] == true) continue; //若next節點已經是集合K的成員
//(dis[next]==dis[newP]+c) && (costs[next]>costs[newP]+cost)該句展現距離相等時取花費少的
if(dis[next] == -1 || dis[next] > dis[newP] + weight ||
((dis[next] == dis[newP] + weight) && (costs[next] > costs[newP] + cost))) {
dis[next] = dis[newP] + weight; //更新距離
costs[next] = costs[newP] + cost; //更新花費
}
}
int min = 9999999;
//循環查找K集合與U集合之間已經計算出dis值得邊的最小邊,另其為新加入點
for(int j=1;j<=n;j++) {
if(mark[j] == true) continue;
if(dis[j] == -1) continue;
if(dis[j] < min){
min = dis[j];
newP = j;
}
}
mark[newP] = true; //将新加入點列入K集合
}
printf("%d %d\n", dis[t], costs[t]);
}
return 0;
}