Dijkstra算法的应用
总是爱犯的一个错误就是在构建图的时候总是构建单个边。害,应该两个边都加进去(因为是无向图)。
#include<iostream> #include<queue> #include<algorithm> #include<vector> #include<limits.h> using namespace std; const int maxn=1001; struct graph{ int to; int l; int w; }; struct Point{ int index; //点的下标 int weight;//源点到此点的距离 Point(int i,int w):index(i),weight(w){} inline bool operator < (const Point &p)const{ return weight>p.weight;//距离近的优先级大 } }; vector<graph> g[maxn]; int dis[maxn]; int path[maxn]; int cost[maxn]; void init(int n){ for(int i=0;i<=n;i++){ dis[i]=INT_MAX; cost[i]=INT_MAX; path[i]=0; g[i].clear(); } } void dijkstra(int s){ priority_queue<Point> q; dis[s]=0; cost[s]=0; q.push(Point(s,dis[s])); while(!q.empty()){ int u=q.top().index; q.pop(); for(int i=0;i<g[u].size();i++){ int to=g[u][i].to; int l=g[u][i].l; int w=g[u][i].w; if(dis[to]>dis[u]+l || (dis[to]==dis[u]+l && cost[to]>cost[u]+w)){ dis[to]=dis[u]+l; cost[to]=cost[u]+w; q.push(Point(to,dis[to])); path[to]=u; } } } } int main(){ int n,m; int a,b,d,p; int s,t; graph temp; while(cin>>n>>m){ if(n==0&&m==0)break; init(n); for(int i=0;i<m;i++){ cin>>a>>b>>d>>p; temp.to=b; temp.l=d; temp.w=p; g[a].push_back(temp); temp.to=a; g[b].push_back(temp); } cin>>s>>t; dijkstra(s); cout<<dis[t]<<" "<<cost[t]<<endl; } return 0; }