我们先看下题目描述：(这道题可以在acwing 上搜索 Dijkstra求最短路 I 来查看额原题额，顺便也把链接放这吧，就是不知道进不进得去，进不去就自己去acwing 上搜索。Dijkstra求最短路 I)
本着下面这个原则，最终成功拿下了！
while(有bug){ 改bug if（accept）break; }
贴心时刻
担心各位老板测试时不想一个一个的输入，我特地把输入输出样例写了下来，各位老板直接复制即可！
输入样例:
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3
同时，也担心各位老板难以滑动代码，我还特地的准备了图片版！
然后上源代码：
#include<bits/stdc++.h> using namespace std; #define maxn 510 //g数组存的是邻接矩阵,d数组存的是某点到起点的最短距离， //st数组是用来装确定了的点（确定了到起点的距离最短的点） int g[maxn][maxn],d[maxn],st[maxn]; int n,m; int dijkstra(){ memset(d,0x3f,sizeof(d));//先将所有距离设为最大 d[1]=0;//起点到起点的距离为0 for(int i=0;i<n;i++){//找出每个点到起点的距离,每次寻找不在st中距离最近的点t int t=-1;//用于更新第一个点，这个比较巧妙 for(int j=1;j<=n;j++){//寻找不在st中，距离最近的点t if(!st[j]&&(t==-1||d[j]<d[t])) t=j; } st[t]=true;//将t加入到st中，表示已经确定了这个点 for(int j=1;j<=n;j++){//通过t点来更新其它点的距离 d[j]=min(d[j],d[t]+g[t][j]); } } d[n]!=0x3f3f3f3f?cout<<d[n]:cout<<-1;//输出答案 return 0; } int main(){ cin>>n>>m; memset(g,0x3f,sizeof(g));//因为是求的最小值，所以初始化为无穷大 while(m--){ int a,b,c; cin>>a>>b>>c; g[a][b]=min(g[a][b],c); //在重边中去取得最小值 } dijkstra();//调用 return 0; }
