dijkstra模板

痛定思痛。 2023-08-17 16:26 111阅读 0赞

题目链接：

[https://nanti.jisuanke.com/t/41349][https_nanti.jisuanke.com_t_41349]

代码：

#include<bits/stdc++.h>
    #define LL long long
    #define Mixsum 1000000 //最大边数 
    #define Mixn 10000 //最大点数 
    using namespace std;
    int n,m,s,k,c;//分别表示点的个数、有向边的个数
    int S;//起点 
    int K[1010];
    LL len[1010];
    LL dis[Mixn+100];//表示存入的已经求得最短路的点
    LL ff[1010][1010];
    bool vis[Mixn+100];//防止走多次 
    struct Node{
        int to,next;
        LL w;
    }edge[Mixsum+100];//存双向边要乘以2 
    int cnt;
    int head[Mixn+100];//存点 
    void add(int p,int q,int w){
        edge[cnt].to=q;
        edge[cnt].next=head[p];
        edge[cnt].w=w;
        head[p]=cnt++;
    }
    struct Jie{
        LL fi;
        int se;//se为边的尾结点，fi为权值 
        bool operator < (const Jie &a)const {
            return fi > a.fi;         // 从小到大  ，x小的优先级别高
        }
    };
    void dijkstra(){
        for(int i=1;i<=n;i++){
            dis[i]=2e9;//初始化，非常重要 ，一些题目可能要初始化多次 
        } 
        priority_queue<Jie>q;//优先队列
        memset(vis,false,sizeof(vis)); 
        dis[S] = 0;
        Jie n1;
        n1.fi = 0;//权值 
        n1.se = S;//后点 
        q.push(n1);
        while (!q.empty())
        {
            Jie n2 = q.top();
            int now = n2.se;
            q.pop();
            if(vis[now]){
        //如果走过，直接跳过 
                continue;
            }
            vis[now]=true;
            for (int i = head[now]; ~i; i = edge[i].next)
            {
                LL c = dis[now] + edge[i].w;
                int d = edge[i].to;
                if (c < dis[d])
                {
                    dis[d] = c;
                    Jie n3;
                    n3.fi = dis[d];
                    n3.se = d;
                    q.push(n3);
                }
            }
        }
    }
    int main(){
        int t;
        scanf("%d",&t);
        while(t--){
        cnt=0;
        memset(head,-1,sizeof(head));
        memset(ff,0,sizeof(ff));
        scanf("%d%d%d%d%d",&n,&m,&s,&k,&c);//先输入n，在初始化 
        for(int i=1;i<=n;i++) len[i]=2e9;
        for(int i=1;i<=k;i++) scanf("%d",&K[i]);//起点
        int p,q;
        LL w;
        for(int i=1;i<=m;i++){
            scanf("%d%d%lld",&p,&q,&w);
            if(ff[p][q]==0){
                add(p,q,w);
                add(q,p,w);
                ff[p][q]=w;
                ff[q][p]=w;
            }
            else{
                if(ff[p][q]>w){
                add(p,q,w);
                add(w,p,q);
                ff[p][q]=w;
                ff[q][p]=w;    
                }
            }
        }
        LL M1=0,M2=0;
        for(int i=1;i<=k;i++){
            S=K[i];
            dijkstra();
            for(int j=1;j<=n;j++){
                if(dis[j]!=2e9) len[j]=min(len[j],dis[j]);
            }
        }
        for(int i=1;i<=n;i++){
            if(len[i]!=2e9) M1=max(len[i],M1);
        }
        S=s;
        dijkstra();
        for(int i=1;i<=n;i++){
            //cout<<dis[i]<<endl;
            if(dis[i]!=2e9) M2=max(M2,dis[i]);
        }
        //cout<<M1<<" "<<M2<<endl; 
        if(M1*(LL)c>=M2){
            printf("%lld\n",M2);
        }
        else{
            printf("%lld\n",M1);
        }
        }
        return 0; 
    }

转载于:https://www.cnblogs.com/Aiahtwo/p/11508093.html

[https_nanti.jisuanke.com_t_41349]: https://nanti.jisuanke.com/t/41349