题意：N和M(0<N<200,0<M<1000)，分别代表现有已修建的道路的数目和城镇的数目，城镇分别以0～M-1编号。接下来N条道路 A, B, X (0<=A,B<N,A!=B,0<X<10000) ，
两个整数S,T(0<=S,T<N)，分别代表起点和终点。如果数据不存在则输出-1
思路：使用优先队列优化的迪杰斯特拉算法，由于输入中还有重边问题，用链式向前星(没有处理的情况下)就会有错，所以我们用vector存储的邻接表 来存储
完整代码：
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <queue> #include <algorithm> #define inf 0x3f3f3f3f #define maxn 1010 using namespace std; int dist[maxn],n,t; struct edge { int to; int cost; }; vector<edge> g[maxn];//邻接表 typedef pair<int,int> pi; void dijkstra(int s) { //通过指定greater<pi>参数，堆按照first从大到小的顺序取初值 priority_queue<pi,vector<pi>,greater<pi> > que; memset(dist,inf,sizeof(dist)); dist[s]=0; que.push(pi(0,s)); while(!que.empty()) { pi p = que.top(); que.pop(); int v = p.second;//first是最短距离，second是顶点的编号 if(dist[v]<p.first) continue; for(int i=0; i<g[v].size(); ++i) { edge e=g[v][i]; if(dist[e.to]>dist[v]+e.cost)//Dijkstra { dist[e.to]=dist[v]+e.cost; que.push(pi(dist[e.to],e.to)); } } } } int main() { int a,b,l; while(scanf("%d%d",&t,&n)!=EOF) { for(int i=0; i<t; i++) { scanf("%d%d%d",&a,&b,&l); edge A; A.cost = l,A.to = b; edge B; B.cost = l,B.to = a; g[a].push_back(A); g[b].push_back(B); } dijkstra(n); printf("%d\n",dist[1]); } return 0; }
转载于:https://www.cnblogs.com/Tianwell/p/11281944.html
