只是为了熟悉一下最短路径代码打的,这个题目是dijkstra算法的模版代码。我先看懂意思,然后自己敲了。
#include <cstdio> #include <iostream> #include <cstring> #include <queue> #include <algorithm> using namespace std; const int maxn = 210; const int maxm = 2010; typedef pair<int,int> pii; int v[maxm],next[maxm],w[maxm]; int first[maxn],d[maxn],e; void init() { e = 0; memset(first,-1,sizeof(first)); } void add_edge(int a,int b,int c) { v[e] = b;next[e] = first[a];w[e] = c;first[a] = e++; } void dij(int src) { priority_queue <pii,vector<pii>,greater<pii> > q; memset(d,-1,sizeof(d)); d[src] = 0; q.push(make_pair(0,src)); while(!q.empty()){ int u = q.top().second; q.pop(); for(int i = first[u];i != -1;i = next[i]){ if(d[v[i]] == -1 || d[v[i]] > d[u]+w[i]){ d[v[i]] = d[u]+w[i]; q.push(make_pair(d[v[i]],v[i])); } } } } int main(){ int n,m,s,t,a,b,c; while(cin >> n >> m) { init(); for(int i = 0;i < m;i++){ cin >> a >> b >> c; add_edge(a,b,c); add_edge(b,a,c); } cin >> s >> t; dij(s); cout << d[t] << endl; } return 0; }