最短路模板

xls的dij模板

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=1e3+5;
const int inf=1e9;
struct node{
    int u,d;
    node(int u,int d):u(u),d(d){}
    bool operator <(const node &a)const{
        return d>a.d;
    }
};
priority_queue<node>q;
vector<int>G[N],dis[N];
int vis[N],d[N];
void init(){
    for(int i=1;i<N;i++)
    G[i].clear(),dis[i].clear();
    for(int i=1;i<N;i++)
    vis[i]=0,d[i]=inf;
    while(!q.empty())q.pop();
}
int dij(){
    while(!q.empty()){
        node e=q.top();
        q.pop();
        int u=e.u;
        if(vis[u]==1)continue;
        if(vis[u]==2)return e.d;
        vis[u]=1;
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i];
            if(d[v]>d[u]+dis[u][i]){
                d[v]=d[u]+dis[u][i];
                q.push(node(v,d[v]));
            }
        }
    }
}
int main(){
    int T,S,D,u,v,w;
    while(~scanf("%d%d%d",&T,&S,&D)){
        init();
        for(int i=0;i<T;i++){
            scanf("%d%d%d",&u,&v,&w);
            G[u].push_back(v);
            G[v].push_back(u);
            dis[u].push_back(w);
            dis[v].push_back(w);
        }
        for(int i=0;i<S;i++){
            scanf("%d",&u);
            q.push(node(u,0));
            d[u]=0;
        }
        for(int i=0;i<D;i++){
            scanf("%d",&u);
            vis[u]=2;
        }
        printf("%d
",dij()); 
    }
}