选择某一个点开始,每次去找这个点的最短边,然后再从这个开始不断迭代,更新距离.

代码:

1. 朴素(vector存图)

   #include <iostream>
   
   #include <cstdio>
   
   #include <cstring>
   
   #include <cmath>
   
   #include <algorithm>
   
   #include <stack>
   
   #include <queue>
   
   #include <vector>
   
   #include <map>
   
   #include <set>
   
   #include <unordered_set>
   
   #include <unordered_map>
   
   #define ll long long
   
   #define fi first
   
   #define se second
   
   #define pb push_back
   
   #define me memset
   
   const int N = 1e6+10;
   
   const int mod = 1e9 + 7;
   
   const int INF = 0x3f3f3f3f;
   
   using namespace std;
   
   typedef pair<int,int> PII;
   
   typedef pair<ll,ll> PLL;
   
   int n,m,s;
   
   struct misaka{
   
      int to;
   
      int val;
   
   }p;
   
   vector<misaka> v[N];
   
   int dis[N];
   
   bool st[N];
   
    void dijkstra(){
   
       me(dis,INF,sizeof(dis));
   
       dis[s]=0;
   
       for(int i=0;i<n;++i){
   
           int t=-1;
   
           for(int j=1;j<=n;++j){
   
               if(!st[j] && (t==-1 || dis[t]>dis[j])) t=j;  //确定路径最短的点
   
           }
   
           st[t]=true;
   
           for(auto w:v[t]){
   
               dis[w.to]=min(dis[w.to],dis[t]+w.val);
   
           }
   
       }
   
    }
   
   int main() {
   
       ios::sync_with_stdio(false);cin.tie(0);
   
       cin>>n>>m>>s;
   
       while(m--){
   
          int a;
   
          cin>>a;
   
          cin>>p.to>>p.val;
   
          v[a].pb(p);
   
       }
   
       dijkstra();
   
       for(int i=1;i<=n;++i){
   
           cout<<dis[i]<<" ";
   
       }
   
       return 0;
   
   }
   
   

2. 堆(优先队列)优化

   #include <iostream>
   
   #include <cstdio>
   
   #include <cstring>
   
   #include <cmath>
   
   #include <algorithm>
   
   #include <stack>
   
   #include <queue>
   
   #include <vector>
   
   #include <map>
   
   #include <set>
   
   #include <unordered_set>
   
   #include <unordered_map>
   
   #define ll long long
   
   #define fi first
   
   #define se second
   
   #define pb push_back
   
   #define me memset
   
   const int N = 1e6 + 10;
   
   const int mod = 1e9 + 7;
   
   const int INF = 0x3f3f3f3f;
   
   using namespace std;
   
   typedef pair<int,int> PII;
   
   typedef pair<ll,ll> PLL;
   
    struct misaka{
   
       int out;
   
       int val;
   
    }e;
   
   int n,m,s;
   
   int dis[N];
   
   bool st[N];
   
   vector<misaka> v[N];
   
    void dijkstra(){
   
       me(dis,INF,sizeof(dis));
   
       dis[1]=0;
   
       priority_queue<PII,vector<PII>,greater<PII>> h;
   
       h.push({0,s});
   
       while(!h.empty()){
   
           auto tmp=h.top();
   
           h.pop();
   
           int num=tmp.se;
   
           int dist=tmp.fi;
   
           if(st[num]) continue;
   
           st[num]=true;
   
           for(auto w:v[num]){
   
               int j=w.out;
   
               if(dis[j]>dist+w.val){
   
                   dis[j]=dist+w.val;
   
                   h.push({dis[j],j});
   
               }
   
           }
   
       }
   
    }
   
   int main() {
   
       ios::sync_with_stdio(false);cin.tie(0);
   
       cin>>n>>m>>s;
   
       while(m--){
   
           int a;
   
           cin>>a>>e.out>>e.val;
   
           v[a].pb(e);
   
       }
   
       dijkstra();
   
       for(int i=1;i<=n;++i){
   
           cout<<dis[i]<<" ";
   
       }
   
       return 0;
   
   }