简单dijkstra算法应用，dijkstra的朴素算法就能a，无需堆优化，但有一个很坑的点，输入存在重边情况，即一条边可能输入两次或多次不同的值，我们只要取最短的一次即可

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define NIL -1
#define INF 0x3f3f3f3fusing namespace std;const int maxn=1e3+10;//这里要注意一下，一开到1e4就Memory Limit Exceed
int n,vis[maxn]/*,parent[maxn]*/,dis[maxn],graph[maxn][maxn];void dijkstra()
{for(int i=1;i<=n;i++){vis[i]=0;;dis[i]=INF;/*parent[i]=NIL;*/}dis[1]=0;while(1){int minv=INF,u=-1;for(int i=1;i<=n;i++){if((!vis[i])&&dis[i]<minv){minv=dis[i];u=i;}}vis[u]=1;if(u==-1)break;for(int v=1;v<=n;v++){if((!vis[v])&&graph[u][v]!=INF){dis[v]=min(dis[u]+graph[u][v],dis[v]);//parent[v]=u;}}}
}int main()
{memset(graph,INF,sizeof(graph));int t;cin>>t>>n;int u,v,w;while(t--){cin>>u>>v>>w;if(w<graph[u][v]){graph[u][v]=graph[v][u]=w;//因为是无向图，因此u到v和v到u的距离置成一个值}}dijkstra();cout<<dis[n]<<endl;return 0;	
}