這是一道最短路的模板的，很裸的模板題可惜我還是沒能1A爱致，是因為我不知道dijkstra需要判斷重復(fù)的邊，dijkstra是利用鄰接矩陣存的值，如果有兩條相同的邊重復(fù)輸入且邊的權(quán)值不同嘱么，那么如果靠后的那條邊權(quán)值比前面的那條大，這個同一條邊的較大的值會覆蓋之前那個較小的值顽悼，那么我們求出的最終路徑就不是最短路徑曼振；
下面貼代碼：
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<math.h>
using namespace std;
int t,n;
const int inf = 1e8;
int map[1010][1010];
int dist[1010];
int s[1010];
void dijkstra(int v)
{
for(int i =1;i<=n;i++)
{
dist[i] = map[v][i];
s[i] = 0;
}
s[v] = 1;dist[v] = 0;
for(int i =0;i<n-1;i++)
{
int min = inf,u = v;
for(int i=1;i<=n;i++)
{
if(!s[i]&&dist[i]<min)
{
min = dist[i];
u = i;
}
}
s[u] = 1;
for(int i = 1;i<=n;i++)
{
if(!s[i] && dist[u] + map[u][i]<dist[i])
{
dist[i] = dist[u] + map[u][i];
}
}
}
}
int main()
{
scanf("%d%d",&t,&n);
for(int i = 1;i<=n;i++)
{
for(int j =1;j<=n;j++)
{
if(i!=j)
{
map[i][j] = inf;
}
}
}
for(int i = 0;i<t;i++)
{
int a,b,cost;
scanf("%d%d%d",&a,&b,&cost);
map[a][b] = min(map[a][b],cost);
map[b][a] = min(map[b][a],cost);
}
dijkstra(1);
printf("%d\n",dist[n]);
}
