任意门：http://acm.hdu.edu.cn/showproblem.php?pid=1874
HD-1874-畅通工程续
Problem Description
某省自从实行了很多年的畅通工程计划后，终于修建了很多路。不过路多了也不好，每次要从一个城镇到另一个城镇时，都有许多种道路方案可以选择，而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。
现在，已知起点和终点，请你计算出要从起点到终点，最短需要行走多少距离。
Input
本题目包含多组数据，请处理到文件结束。
每组数据第一行包含两个正整数N和M(0< N<200,0< M<1000)，分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0～N-1编号。
接下来是M行道路信息。每一行有三个整数A,B,X(0<=A,B< N,A!=B,0< X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。
再接下一行有两个整数S,T(0 <= S,T < N)，分别代表起点和终点。
Output
对于每组数据，请在一行里输出最短需要行走的距离。如果不存在从S到T的路线，就输出-1.
Sample Input
3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2
Sample Output
2
-1
这是Dijkstra算法的模板题
不会这算法的，友情链接http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html
#include <cstdio>
const int N=205;
const int inf=999999;
int i[N][N];
int dis[N];
int pre[N];
void Dijkstra(int n, int v, int *dis, int *pre, int i[N][N])
{bool s[N];for(int a = 0;a < n;a ++){s[a]=0;dis[a]=i[v][a];if(dis[a]==inf)pre[a]=0;elsepre[a]=v;}s[v]=1;dis[v]=0;for(int a = 1;a < n;a ++){int tem=inf;int u=v;for(int b = 0;b < n;b ++){if((!s[b])&&tem>dis[b])//找出当前点到下个点的最小权值{u=b;tem=dis[b];}}s[u]=1;for(int b = 0;b < n;b ++)//更新dis数组{if((!s[b])&&i[u][b]<inf){int news=i[u][b]+dis[u];if(news<dis[b]){dis[b]=news;pre[v]=u;}}}}}
int main()
{int n,m,x,y,l;while(~scanf("%d%d",&n,&m)){for(int a = 0; a < n; a ++)for(int b = 0 ; b < n; b ++){if(a==b)i[a][b]=0;elsei[a][b]=inf;}for(int a = 0; a < m; a ++){scanf("%d%d%d",&x,&y,&l);if(l<i[x][y])i[x][y]=i[y][x]=l;}int s,e;scanf("%d%d",&s,&e);for(int a = 0; a < n; a ++)dis[a]=inf;Dijkstra(n,s,dis,pre,i);if(dis[e]!=inf)printf("%d\n",dis[e]);elseprintf("-1\n");}return 0;
}