http://poj.org/problem?id=3159
思路：用O(V+ElogV)的Dijkstra算法求1到n的最短路。即用优先队列优化Dijkstra算法。
#include <stdio.h>
#include <queue>
#include <string.h>
using namespace std;
const int maxn=;
const int maxm=;
struct node
{
int u,v,w;
int next;
} edge[maxm];
struct pot
{
int v,w;
pot(int v = ,int w = ):v(v),w(w) {}
bool operator < (const pot &a)const
{
return w > a.w;
}
};
int n,m;
int head[maxn],vis[maxn],dis[maxn],cnt;
void add(int u,int v,int w)
{
edge[cnt].u = u;
edge[cnt].v = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt++;
}
void Dijkstra(int s)
{
memset(vis,,sizeof(vis));
memset(dis,,sizeof(dis));
dis[s] = ;
priority_queue<pot>q;
q.push(pot(s,dis[s]));
for(int i = ; i < n; i++)
{
while(!q.empty()&&vis[q.top().v])//去掉队首被标记的点
q.pop();
if (q.empty()) break;
pot pre = q.top();//取出队首的点，即权值最小的点
q.pop();
vis[pre.v] = ;//标记
for (int j = head[pre.v]; j !=-; j= edge[j].next)//找出pre的所有连接点
{
int v = edge[j].v;
if (!vis[v] && dis[pre.v]+edge[j].w < dis[v])//更新所有点到源点的距离
{
dis[v] = dis[pre.v]+edge[j].w;
q.push(pot(v,dis[v]));//将更新后的点与权值入队列
}
} } }
int main()
{
int u,v,w;
cnt = ;
scanf("%d %d",&n,&m);
memset(head,-,sizeof(head));
for (int i = ; i < m; i++)
{
scanf("%d %d %d",&u,&v,&w);
add(u,v,w);
}
Dijkstra();
printf("%d\n",dis[n]);
return ;
}