SPFA和堆优化的Dijk

 1 int dist[maxn];//距离
 2 int g[maxn][maxn];//邻接矩阵存图
 3 bool vis[maxn];//是否访问过
 4 void dijk(int v){//起点v
 5     memset(dist, 0x3f,sizeof dist); 
 6     dist[v]=0;
 7     for(int i=0;i<n;i++) 
 8     {
 9         int t=-1; 
10         for(int j=1;j<=n;j++) 
11             if(!vis[j]&&(t==-1||dist[t]>dist[j]))     
12                 t=j;
13         vis[t]=true;   
14         for(int j=1;j<=n;j++) 
15             dist[j]=min(dist[j],dist[t]+g[t][j]);
16     }
17 }

 1 vector<pair<int,int> > g[maxn];//距离，点标
 2 int dist[maxn];
 3 bool vis[maxn];
 4 void dijk(int v){
 5     memset(dist,0x3f,sizeof(dist));
 6     dist[v]=0;
 7     priority_queue<pair<int,int> >pq;//距离，点标
 8     pq.push({-dist[v],v});//默认大的优先，故取负数使小的优先，也可自定义结构体
 9     while(!pq.empty()){
10         int t=pq.top().second;
11         pq.pop();
12         if(vis[t])   continue;
13         vis[t]=true;
14         for(int i=0; i<g[t].size(); i++){
15             if(dist[g[t][i].second]>dist[t]+g[t][i].first){
16                 dist[g[t][i].second]=dist[t]+g[t][i].first;
17                 pq.push({-dist[g[t][i].second],g[t][i].second});
18             }
19         }
20     }
21 }

 1 vector<pair<int,int> > g[maxn];//点标，距离
 2 int dist[maxn];
 3 bool inq[maxn];
 4 void spfa(int s){
 5     memset(dist,0x3f,sizeof(dist));
 6     queue<int> q;
 7     q.push(s);
 8     inq[s]=1;
 9     dist[s]=0;
10     while(!q.empty()){
11         int t=q.front();
12         q.pop();
13         inq[t]=false;
14         for(int i=0; i<g[t].size(); ++i){
15             int to=g[t][i].first;
16             if(dist[to]>dist[t]+g[t][i].second){
17                 dist[to]=dist[t]+g[t][i].second;
18                 if(inq[to]) continue;
19                 inq[to]=true;
20                 q.push(to);
21             }
22         }
23     }
24 }