算法模板(三)最短路问题

Dijkstra

#include<bits/stdc++.h>
#define maxn 1000
#define maxm 1000
#define X first
#define Y second
using namespace std;
typedef pair<int,int> pall;
struct edge{
    int u,v,w,next;
}E[maxm<<1];
int p[maxn],eid=0;
struct cmp{
    operator ()(const pall &a,const pall &b)const{
        if(a.Y!=b.Y)return a.Y<b.Y;
        return a.X<b.X; 
    }
};
void init(){
    for(register int i=0;i<maxn;i++)p[i]=-1;
    eid=0; 
}
void insert(int u,int v,int w){
    E[eid].u=u;
    E[eid].v=v;
    E[eid].w=w;
    E[eid].next=p[u];
    p[u]=eid++;
}
void insert2(int u,int v,int w){
    insert(u,v,w);
    insert(v,u,w);
}
int n,m;
int dis[maxn],vis[maxn];
void dijkstra(int u){
    for(register int i=0;i<maxn;i++)dis[i]=0x3f3f3f3f,vis[i]=0;
    dis[u]=0;vis[u]=1;
    set<pall,cmp> s;
    s.insert(make_pair(u,0));
    for(register int i=0;i<n && s.size();i++){
        u=s.begin()->X;
        s.erase(*s.begin());
        vis[u]=1;
        for(register int j=p[u];~j;j=E[j].next){
            int v=E[j].v;
            int w=E[j].w;
            if(!vis[v] && dis[v]>dis[u]+w){
                s.erase(make_pair(v,dis[v]));
                s.insert(make_pair(v,dis[v]=dis[u]+w));
            }
        } 
    }
}
int u,v,w;
int main(){
    init();
    cin>>n>>m;
    for(register int i=0;i<m;i++){
        cin>>u>>v>>w;
        insert2(u,v,w);
    }
    dijkstra(1);
    cout<<dis[n]<<endl;
    return 0;
}

SPFA

#include<bits/stdc++.h>
#define maxn 2000
#define maxm 4000
using namespace std;
struct edge{
    int u,v,w,next;
}E[maxm<<1];
int p[maxn],eid;
void init(){
    for(register int i=0;i<maxn;i++)p[i]=-1;
    eid=0;
}
void insert(int u,int v,int w){
    E[eid].u=u;
    E[eid].w=w;
    E[eid].v=v;
    E[eid].next=p[u];
    p[u]=eid++;
}
void insert2(int u,int v,int w){
    insert(u,v,w);
    insert(v,u,w);
}
int n,m;
int dis[maxn],vis[maxn];
void spfa(int u){
    for(register int i=0;i<maxn;i++)dis[i]=0x3f3f3f3f,vis[i]=0;
    dis[u]=0;vis[u]=1;
    queue<int> q;
    q.push(u);
    while(!q.empty()){
        u=q.front();
        q.pop();
        vis[u]=0;
        for(register int i=p[u];~i;i=E[i].next){
            int v=E[i].v;
            int w=E[i].w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            } 
        }
    }
}
int u,v,w;
int main(){
    init();
    cin>>n>>m;
    for(register int i=0;i<m;i++){
        cin>>u>>v>>w;
        insert2(u,v,w);
    }
    spfa(1);
    cout<<dis[n]<<endl;
    return 0;
}

Floyd

#include<bits/stdc++.h>
using namespace std;
int mp[300][300];
int n,m;
int u,v,w;
void floyd(){
    for(register int k=1;k<=n;k++){
        for(register int i=i+1;i<=n;i++){
            for(register int j=1;j<=n;j++)mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
        }
    }
}
int main(){
    cin>>n>>m;
    for(register int i=0;i<m;i++){
        cin>>u>>v>>w;
        mp[u][v]=w;
        mp[v][u]=w;
    }
    floyd();
    cout<<mp[1][n];
    return 0;
}