http://poj.org/problem?id=3159
题意：有向图，第一行n是点数，m是边数，每一行有三个数，前两个是有向边的起点与终点，最后一个是权值，求从1到n的最短路径。
思路：这个题让会神给讲的，用的dijkstra，看的网上很多用SPFA的。
关于SPFA：http://www.cnblogs.com/devtang/archive/2011/08/25/spfa.html
http://blog.csdn.net/chenjiang492943457/article/details/5375413
关于差分约束系统：http://www.cnblogs.com/void/archive/2011/08/26/2153928.html
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue> using namespace std ;
const int maxn = ;
const int maxm = ;
int head[maxn],next[maxm] ;
int map[maxn] ;
bool vis[maxn] ;
const int INF = << ;
int cnt , n , m;
struct node
{
int u ;
int v ;
int c ;
node(){}
node(int u,int v,int c):u(u),v(v),c(c){} }edge[maxm] ; struct node1
{
int v,c ;
node1(){}
node1(int v,int c):v(v),c(c){}
bool operator <(const node1 &a)const
{
return c > a.c ;
}
} ;
void addnode(int u,int v,int c)
{
edge[cnt] = node(u,v,c) ;
next[cnt] = head[u] ;
head[u] = cnt++ ;
} ;
bool relax(int u,int v,int c)
{
if(map[v] > map[u] + c)
{
map[v] = map[u]+c ;
return true ;
}
return false ;
} void Init()
{
memset(head,-,sizeof(head)) ;
memset(next,-,sizeof(next)) ;
cnt = ;
for(int i = ; i < m ; i++)
{
int x,y,z ;
scanf("%d %d %d",&x,&y,&z) ;
addnode(x,y,z) ;
}
} void dija(int sh)
{
memset(vis,,sizeof(vis)) ;
for(int i = ; i <= n ; i++)
map[i] = INF ;
map[sh] = ;
priority_queue<node1>Q ;
Q.push(node1(sh,map[sh])) ;
for(int i = ; i < n ; i++)
{
while(!Q.empty() && vis[Q.top().v]) Q.pop() ;
if(Q.empty()) break ;
node1 temp = Q.top() ;
Q.pop() ;
vis[temp.v] = true ;
for(int j = head[temp.v] ; j != - ; j = next[j])
{
if(relax(temp.v,edge[j].v,edge[j].c) && !vis[edge[j].v])
Q.push(node1(edge[j].v,map[edge[j].v])) ;
}
}
}
int main()
{
while(~scanf("%d %d",&n,&m))
{
Init() ;
dija() ;
printf("%d\n",map[n]) ;
}
return ;
}