有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。
dijkstra算法：
#include <iostream> #include <algorithm> #include <vector> #include <queue> using namespace std; const int INF = 1e9; const int maxn = 510; struct edge{ int from,to,w,l; edge(int a,int b, int c,int d){ from = a; to = b; w = c; l = d; } }; vector<edge> e[maxn]; struct node{ int id; int n_dis; int n_f; node(int a,int b,int c){ id = a; n_dis = b; n_f = c; } bool operator < (const node & a) const { if(n_dis == a.n_dis) return n_f > a.n_f ; else return n_dis > a.n_dis ; } }; int n,m,s,d; int dis[maxn]; int f[maxn]; void dijkstra(){ bool done[maxn]; for(int i = 0;i<n;i++){ dis[i] = INF; f[i] = INF; done[i] = false; } dis[s] = 0; f[s] = 0; priority_queue<node> q; q.push(node(s,dis[s],f[s])); while(!q.empty() ){ node u = q.top() ; q.pop() ; if(done[u.id]) continue; done[u.id] = true; for(int i = 0;i<e[u.id].size() ;i++){ edge y = e[u.id][i]; if(done[y.to]) continue; if(dis[y.to] > y.w+u.n_dis){ dis[y.to] = y.w+u.n_dis; f[y.to] = y.l+u.n_f; q.push(node(y.to,dis[y.to],f[y.to])) ; } else if(dis[y.to] == y.w+u.n_dis){ //核心代码 if(f[y.to] > y.l+u.n_f){ dis[y.to] = y.w+u.n_dis; f[y.to] = y.l+u.n_f; q.push(node(y.to,dis[y.to],f[y.to])) ; } } } } } int main(){ cin >> n >> m >> s >> d; int x,y,sv,len; for(int i = 0;i<m;i++){ cin >> x >> y >> sv >> len; e[x].push_back(edge(x,y,sv,len)) ; e[y].push_back(edge(y,x,sv,len)) ; } dijkstra() ; cout << dis[d] << " " << f[d] << endl; return 0; }