题目链接
AC代码
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
int t,n;
const int N = 1010;
int g[N][N];
int dist[N];
int st[N];
int Dijstra()
{
memset(dist, 0x3f,sizeof dist);
memset(st,0, sizeof st);
dist[1] = 0;
for(int i=0; i<n; i++)
{
int t = -1;
for(int j=1; j<=n; j++)
{
if(!st[j]&&(t==-1||dist[t]>dist[j])) t = j;
}
st[t] = 1;
for(int j=1; j<=n; j++)
{
dist[j] = min(dist[j],g[t][j]+dist[t]);
}
}
return dist[n];
}
int main(){
cin>>t>>n;
memset(g,0x3f, sizeof g);
for(int i=0; i<t; i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
g[u][v] = g[v][u] = min(g[u][v],w);
}
printf("%d\n",Dijstra());
return 0;
}