题意：给定一个有向图，多个起点，一个终点，求起点到终点的最短路。
这道题TLE了好多次，两侧次的对比主要在于对起点的处理上，法一：最开始是采用的hdu2066——一个人的旅行，这道题的方法做的，发现总是TLE。
法二：然后看别人的博客：再加上一个点作为起点，编号为0，这个点和题中给的那些起点之间的距离为0。这样题目就转化为了求单源最短路径问题。
当时我觉得这两种做法没有什么不同，结果我错了。法一：每个起点都要去运行一边 Dijkstra算法，而法二：只用运行一次Dijkstra算法，所以法一总是超时。
接下来给出两次的代码：
法一：
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
const int Max = 1010;
const int INF = 0xFFFFFFF;
int value[Max][Max];
int vis[Max];
int dis[Max];
int s[Max];
int T,S,D;
void init(){
for(int i = 1 ; i <= T ; i++){
for(int j = 1 ; j <= T ; j++)
value[i][j] = INF;//初始化点与点之间的距离
}
}
void Dijkstra(int s)
{
int pos;//?
int i,j;
memset(vis,0,sizeof(vis));
for( i=1;i<=T;i++)
dis[i]=INF;
dis[s]=0;
for( i = 1;i<=T;i++)
{
pos = -1;
for( j=1;j<=T;j++)
{
if(!vis[j]&&(pos==-1||dis[j]<dis[pos]))
pos=j;//?
}
if(pos == -1)
break;
vis[pos]=1;
for( j=1;j<=T;j++)
{
if(!vis[j]&&dis[j]>dis[pos]+value[pos][j])
dis[j]=dis[pos]+value[pos][j];
}
}
}
int main()
{
int a,b,v,ans,i;
while(~scanf("%d%d%d",&T,&S,&D))
{
init();
memset(s,0,sizeof(s));
// for(int i=1;i<=T;i++)
// v[i]=i;
for( i=0; i<S; i++)
{
scanf("%d%d%d",&a,&b,&v);
if(value[a][b] > v) //要是有相同边，保存最短的边
value[a][b]=v;
}
int w;
scanf("%d",&w);
for( i=0;i<w;i++)
scanf("%d",&s[i]);
//枚举
ans = INF;
for( i=0;i<w;i++)
{
Dijkstra(s[i]);
ans = ans<dis[D]? ans : dis[D];
}
if(ans!=INF)
printf("%d\n",ans);
else
printf("-1\n");
}
return 0;
}法二：
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
const int Max = 1010;
const int INF = 0xFFFFFFF;
int value[Max][Max];
int vis[Max];
int dis[Max];
int T,S,D;
void init(){
for(int i = 0 ; i <= T ; i++){
for(int j = 0 ; j <= T ; j++)
value[i][j] = INF;//初始化点与点之间的距离
}
}
void Dijkstra(int s)
{
int pos;//?
int i,j;
memset(vis,0,sizeof(vis));
for( i=0;i<=T;i++)
dis[i]=INF;
dis[s]=0;
for( i = 0;i<=T;i++)
{
pos = -1;
for( j=0;j<=T;j++)
{
if(!vis[j]&&(pos==-1||dis[j]<dis[pos]))
pos=j;//?
}
if(pos == -1)
break;
vis[pos]=1;
for( j=0;j<=T;j++)
{
if(!vis[j]&&dis[j]>dis[pos]+value[pos][j])
dis[j]=dis[pos]+value[pos][j];
}
}
}
int main()
{
int a,b,v,i;
int s;
while(~scanf("%d%d%d",&T,&S,&D))
{
init();
for( i=0; i<S; i++)
{
scanf("%d%d%d",&a,&b,&v);
if(value[a][b] > v) //要是有相同边保存最短的边
value[a][b]=v;
}
int w;
scanf("%d",&w);
for(i=0;i<w;i++)
{
scanf("%d",&s);
value[0][s]=0;
}
Dijkstra(0);
if(dis[D]!=INF)
printf("%d\n",dis[D]);
else
printf("-1\n");
}
return 0;
}