简单dijkstra算法应用，dijkstra的朴素算法就能a，无需堆优化，但有一个很坑的点，输入存在重边情况，即一条边可能输入两次或多次不同的值，我们只要取最短的一次即可
#include<iostream> #include<cstring> #include<algorithm> #include<vector> #include<queue> #define NIL -1 #define INF 0x3f3f3f3f using 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; }