You are given a weighted undirected graph. The vertices are enumerated from 1 to n. Your task is to find the shortest path between the vertex 1 and the vertex n.
Input
The first line contains two integers n and m (2 ≤ n ≤ 105, 0 ≤ m ≤ 105), where n is the number of vertices and m is the number of edges. Following m lines contain one edge each in form ai, bi and wi (1 ≤ ai, bi ≤ n, 1 ≤ wi ≤ 106), where ai, bi are edge endpoints and wi is the length of the edge.
It is possible that the graph has loops and multiple edges between pair of vertices.
Output
Write the only integer -1 in case of no path. Write the shortest path in opposite case. If there are many solutions, print any of them.
Sample Input
5 6 1 2 2 2 5 5 2 3 4 1 4 1 4 3 3 3 5 1
Sample Output
1 4 3 5
解题思路
题意很简单，就是普通的求1到N 的最短路径，但是数据比较大，N<=100000,M<=100000,W<=1000000，最大程度可能为1e11。如果用简单的裸Dijsktra（o(n^2)）必定超时，所以要用堆优化。 当然如果用SPFA的话，就可以直接用，只需中途判断下大小以决定是否继续。
AC代码1(SPFA)：
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <cstring> using namespace std; #define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) typedef long long ll; const ll INF = 0x3f3f3f3f3f3f3f3f; const int MAXN = 100005; int n,m,vis[MAXN],path[MAXN],p[MAXN]; ll dis[MAXN]; struct Node { int to,cost; }; vector<Node> v[MAXN]; void spfa() { fill(dis,dis+MAXN,INF); fill(vis,vis+MAXN,false); queue<int> q; q.push(1); dis[1]=0; vis[1]=true; while(!q.empty()) { int x=q.front(); q.pop(); vis[x]=false; if(dis[x]>dis[n]) continue; // 如果满足条件就没必要继续这一层了 int len=v[x].size(); for(int i=0;i<len;i++) { int to=v[x][i].to; if(dis[to]>dis[x]+v[x][i].cost) { dis[to]=dis[x]+v[x][i].cost; path[to]=x; if(!vis[to]) { vis[to]=true; q.push(to); } } } } } int main() { int a,b,w; Node node; scanf("%d%d",&n,&m); for(int i=0;i<m;i++) { scanf("%d%d%d",&a,&b,&w); node.to=b,node.cost=w; v[a].push_back(node); node.to=a; v[b].push_back(node); } spfa(); if(dis[n]==INF) cout << -1 << endl; else { int j=0; while(n) { p[j++]=n; n=path[n]; } for(int i=j-1;i>=0;i--) cout << p[i] << (i==0?'\n':' '); } return 0; }AC代码2(dijkstra)：
#include <iostream> #include <algorithm> #include <queue> #include <vector> using namespace std; #define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) typedef long long ll; const ll INF = 0x3f3f3f3f3f3f3f3f; const int MAXN = 100005; int n,m,path[MAXN]; ll dis[MAXN]; bool vis[MAXN]; vector<pair<int,int> > v[MAXN]; void dijkstra() { fill(vis,vis+MAXN,false); fill(dis,dis+MAXN,INF); dis[1]=0; priority_queue<pair<ll,int> > q; q.push(make_pair(0,1)); while(!q.empty()) { int x=q.top().second; q.pop(); if(vis[x]) continue; int len=v[x].size(); for(int i=0;i<len;i++) { int to=v[x][i].first; ll cost=v[x][i].second; if(dis[to]>dis[x]+cost) { dis[to]=dis[x]+cost; q.push(make_pair(-dis[to],to)); path[to]=x; } } } } int main() { SIS; int a,b,c; cin >> n >> m; for(int i=0;i<m;i++) { cin >> a >> b >> c; v[a].push_back(make_pair(b,c)); v[b].push_back(make_pair(a,c)); } dijkstra(); if(dis[n]==INF) cout << -1 << endl; else { vector<int> ans; while(n) { ans.push_back(n); n=path[n]; } int len=ans.size(); for(int i=len-1;i>=0;i--) cout << ans[i] << (i==0?'\n':' '); } return 0; }