传送门：http://acm.hdu.edu.cn/showproblem.php?pid=2544
思路：最短路的模板题
Dijkstra 算法是一种类似于贪心的算法，步骤如下：
1、当到一个点时，图上部分的点的最短距离已确定，部分点的最短距离未确定。
2、选一个所有未确定点中离源点最近的点，把它认为成最短距离。
3、再把这个点所有出边遍历一边，更新所有的点。
朴素算法（适用于稠密图 复杂度）
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 105;
const int INF = 9999999;
int w[maxn][maxn];
int dis[maxn];
bool vis[maxn];
int n, m;
void dijkstra()
{
for(int i = 1; i <= n; i++)
vis[i] = false;
for(int i = 1; i <= n; i++)
dis[i] = (i == 1 ? 0 : INF);
for(int i = 1; i <= n; i++)
{
int x, m = INF;
for(int y = 1; y <= n; y++)
{
if(!vis[y] && dis[y] <= m)
m = dis[x = y];
}
vis[x] = true;
for(int y = 1; y <= n; y++)
{
dis[y] = min(dis[y], dis[x] + w[x][y]);
}
}
}
int main()
{
while(scanf("%d%d", &n, &m) != EOF)
{
if(n == m && n == 0)
break;
else
{
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
w[i][j] = INF;
for(int i = 1; i <= m; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
w[a][b] = c;
w[b][a] = c;
}
}
dijkstra();
cout << dis[n] << endl;
}
}优先队列优化（适用于稀疏图 复杂度E*log(V)）
#include<iostream>
#include<queue>
using namespace std;
const int maxn = 2e5 + 10;
const int INF = 0x3f3f3f3f;
struct heapnode
{
int d;
int u;
//结构体内嵌函数，速度较快
bool operator <(const heapnode &a) const
{
return d > a.d;
}
};
struct node
{
int to;
int cost;
int next;
};
node edges[maxn << 1];
int head[maxn];
int d[maxn];
bool vis[maxn];
int n, m;
int tot;
void add_edges(int u, int v, int cost)
{
edges[++tot].to = v;
edges[tot].cost = cost;
edges[tot].next = head[u];
head[u] = tot;
}
void dijkstra()
{
priority_queue<heapnode>q;
for(int i = 1; i <= n; i++)
d[i] = INF, vis[i] = 0;
d[1] = 0;
q.push((heapnode)
{
0, 1
});
while(!q.empty())
{
heapnode x = q.top();// 每次取出d值最小的点
q.pop();
int u = x.u;
if(vis[u])
continue;
vis[u] = 1;
for(int i = head[u]; i; i = edges[i].next)
{
node v = edges[i];
if(d[v.to] > d[u] + v.cost)
{
d[v.to] = d[u] + v.cost;
q.push((heapnode)
{
d[v.to], v.to
});
}
}
}
}
int main()
{
while(scanf("%d %d", &n, &m) != EOF)
{
if(n == m && n == 0)
break;
else
{
tot = 0;
for(int i = 1; i <= n; i++)
head[i] = 0;
for(int i = 1; i <= m; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add_edges(a, b, c);
add_edges(b, a, c);
}
dijkstra();
cout << d[n] << endl;
}
}
}