题目链接：http://codeforces.com/problemset/problem/20/C
思路：需要用优化过的dijkstra，提供两种写法。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define TR(iter, c) for (__typeof(c.begin()) iter = c.begin(); iter != c.end(); ++iter)
using namespace std; const int MAX_N = (100000 + 100);
const long long inf = 1LL << 60;
int N, M, pre[MAX_N];
long long dist[MAX_N]; struct cmp {
bool operator() (const int &p1, const int &p2) const {
return dist[p1] <= dist[p2];
}
};
vector<pair<int, int > > g[MAX_N];
set<int, cmp> q; void Dijkstra()
{
dist[1] = 0;
q.insert(1);
while (!q.empty()) {
int u = *q.begin();
q.erase(q.begin());
REP(i, 0, (int)g[u].size()) {
int v = g[u][i].first, w = g[u][i].second;
if (dist[u] + w < dist[v]) {
q.erase(v);
dist[v] = dist[u] + w;
pre[v] = u;
q.insert(v);
}
}
}
} void dfs(int u)
{
if (u != 1) dfs(pre[u]);
printf("%d ", u);
}
int main()
{
cin >> N >> M;
FOR(i, 1, N) dist[i] = inf;
FOR(i, 1, M) {
int u, v, w; cin >> u >> v >> w;
g[u].push_back(make_pair(v, w));
g[v].push_back(make_pair(u, w));
}
Dijkstra();
if (dist[N] >= inf) { puts("-1"); return 0; }
dfs(N);
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
using namespace std; const int MAX_N = (100000 + 100);
const long long inf = 1LL << 60;
int N, M, pre[MAX_N], vis[MAX_N];
long long dist[MAX_N]; struct cmp {
bool operator() (const pair<long long, int>&p, const pair<long long, int>&q) const {
return p.first >= q.first;
}
};
vector<pair<int, int > > g[MAX_N];
priority_queue<pair<long long, int>, vector<pair<long long, int> >, cmp> pq; void Dijkstra()
{
pq.push(make_pair(dist[1] = 0, 1));
while (!pq.empty()) {
pair<long long, int> p = pq.top();
pq.pop();
if (vis[p.second]) continue;
vis[p.second] = 1;
REP(i, 0, (int)g[p.second].size()) {
int v = g[p.second][i].first, w = g[p.second][i].second;
if (p.first + w < dist[v]) {
dist[v] = p.first + w;
pre[v] = p.second;
if (!vis[v]) pq.push(make_pair(dist[v], v));
}
} }
} void dfs(int u)
{
if (u != 1) dfs(pre[u]);
printf("%d ", u);
}
int main()
{
cin >> N >> M;
FOR(i, 1, N) dist[i] = inf, vis[i] = 0;
FOR(i, 1, M) {
int u, v, w; cin >> u >> v >> w;
g[u].push_back(make_pair(v, w));
g[v].push_back(make_pair(u, w));
}
Dijkstra();
if (dist[N] >= inf) { puts("-1"); return 0; }
dfs(N);
return 0;
}