本文主要是介绍Road ConstructionAOJ2249，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接
思路：简单的dijkstra算法，最短路径计算时顺便递推最小花费
分享一个错误思路：在路径计算时小于和等于最短路径的情况没有区分，都按照cost[r.to] = min(cost[r.to], r.cost);计算，错误原因是之前可能存了一个小值，但不是最短路径对应的值
#include <cstdio>
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
const int MAX = 20010;
const int maxn = 20010;
const int INF = 1e9;using namespace std;struct road_{int to, dis, cost;road_ (){}road_ (int a, int b, int c){to = a;dis =b;cost=c;}
};
typedef pair <int, int> P;
vector <road_> road[MAX];int N, M;
int cost[MAX];
int dis[MAX];//思路： dijkstra算法，在更新最短距离时，如果最短距离相等，保留最小的花费
void Dijkstra(){fill(dis, dis+MAX, INF);fill(cost, cost+MAX, INF);dis[1] = 0;cost[1]=0;priority_queue <P, vector<P>, greater<P> > que;que.push(P(0,1));while(!que.empty()){P p = que.top();int v = p.second;que.pop();if(dis[v] < p.first)continue;//更新距离 for(int i=0; i<road[v].size(); i++){road_ r = road[v][i];if(dis[r.to] < dis[v] + r.dis) continue;//如果小于最短距离，更新距离入队,更新花费 if(dis[r.to] > dis[v] + r.dis) {dis[r.to] = dis[v] + r.dis;cost[r.to] = r.cost;que.push(P(dis[r.to], r.to));}//等于最短距离，比较大小elsecost[r.to] = min(cost[r.to], r.cost);} }
}//测试函数
int main(){
/* ifstream cin ("D:\\钢铁程序员\\程序数据\\067道路修建.txt");//从文件读取数据流，省去手动输入的麻烦 if(!cin){//读取如果失败 cout << "ERROR" << endl;}*/int n,m,a,b,c,d;while(cin>>n>>m){if(n==0&&m==0) break;for(int i=0;i<maxn;i++) road[i].clear();for(int i=0;i<m;i++){cin >> a >> b >> c >> d;road[a].push_back(road_(b,c,d));road[b].push_back(road_(a,c,d));}Dijkstra();int sum = 0;for(int i=1; i<=n; i++)sum += cost[i];cout << sum << endl;}// cin.close();return 0;
}
这篇关于Road ConstructionAOJ2249的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
