最短路径：初涉Dijkstra算法

时间：2022-12-24 15:09:56

模板题目：https://www.luogu.com.cn/problem/P1339

我的代码：

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #define INF 0x3f3f3f3f;

 using namespace std;

 int n,m,s,t;

 int w[][];//初始化为INF

 int d[];

 int vis[];

 int main()

 {

     freopen("input.txt","r",stdin);

     cin>>n>>m>>s>>t;

     memset(vis,,sizeof(vis));

     for(int i=;i<n;i++) d[i]=(i==s-)?:INF;//0赋值给起点

     for(int i=;i<n;i++) for(int k=;k<n;k++) w[i][k]=INF;

     //

     int a,b,p;

     for(int i=;i<m;i++)

     {

         cin>>a>>b>>p;

         a--;b--;//由于输入文件里是[1,n],而模板中是[0,n)所以找了好久才发现

         if(w[a][b]>p){w[b][a]=w[a][b]=p;}

     }

     //

     for(int i=;i<n;i++)

     {

         int x,m=INF;

         for(int y=;y<n;y++)if(!vis[y]&&d[y]<=m)m=d[x=y];

         vis[x]=;

         for(int y=;y<n;y++)d[y]=min(d[y],d[x]+w[x][y]);

     }

     printf("%d\n",d[t-]);

     return ;

 }

其他博主的文章：

https://blog.****.net/m0_38004914/article/details/81209125

https://blog.****.net/kprogram/article/details/81225176

OK

相关文章