这是一道最短路的模板的，很裸的模板题可惜我还是没能1A，是因为我不知道dijkstra需要判断重复的边，dijkstra是利用邻接矩阵存的值，如果有两条相同的边重复输入且边的权值不同，那么如果靠后的那条边权值比前面的那条大，这个同一条边的较大的值会覆盖之前那个较小的值，那么我们求出的最终路径就不是最短路径；
下面贴代码：
#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]);
}
