Output The output contains one line for each data set : the least time Kiki needs to spend ,if it’s impossible to find such a route ,just output “-1”.
Sample Input
5 8 5
1 2 2
1 5 3
1 3 4
2 4 7
2 5 6
2 3 5
3 5 1
4 5 1
2
2 3
4 3 4
1 2 3
1 3 4
2 3 2
1
1
Sample Output
1
-1
題意：琪琪想要去拜訪她的朋友，但是這貨容易暈車，所以要找一個花費時間最少的路線。現在給你路線圖，讓你找出從她家附近的起點站（可以有多個）到朋友家附近的終點站（只有一個）花費時間最少的路線。各個站點的編號從1到n。 思路：最開始我是直接無腦用DIJ算法做的結果絲毫不意外（TLE）了，FUCK。看了看別人的思路才造應該把終點當起點反向構圖，注意，這是個單向圖。 AC代碼：
#include
#include
#define INF 0x3f3f3f3f
#include
using namespace std;
int vis[1010],map[1010][1010],dis[1010],n,ans[1010],num,beg;
void init(){
for(int i=1;i<=n;i++)
for(int j=0;j<=n;j++){
if(i==j)
map[i][j]=map[j][i]=0;
else
map[i][j]=map[j][i]=INF;
}
}
void dijkstra(){
int k=0,flag=0,i;
memset(vis,0,sizeof(vis));
for(i=1;i<=n;i++)
dis[i]=map[beg][i];
vis[beg]=1;
for(i=1;i<=n;i++){
int j,key,temp=INF;
for(int j=1;j<=n;j++)
if(!vis[j]&&temp>dis[j])
temp=dis[key=j];
if(temp==INF){
break;
}
vis[key]=1;
for(int j=1;j<=n;j++)
if(!vis[j]&&dis[j]>dis[key]+map[key][j])
dis[j]=dis[key]+map[key][j];
}
}
int main(){
int m;
while(scanf(%d%d%d,&n,&m,&beg)!=EOF){
int i;
memset(ans,INF,sizeof(INF));
init();//注意要初始化。
for(i=1;i<=m;i++){
int a,b,cost;
scanf(%d%d%d,&a,&b,&cost);
if(map[b][a]>cost)//過濾掉相同的邊。反向構圖。
map[b][a]=cost;
}
scanf(%d,&num);
dijkstra();//直接找到各個終點的位置。
for(i=0;i
