欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【洛谷】P1821 [USACO07FEB] Cow Party S(单源最短路)

程序员文章站 2022-07-13 11:29:31
...

题目描述

寒假到了,nn头牛都要去参加一场在编号为 xx 的牛的农场举行的派对,农场之间有 mm 条有向路,每条路都有一定的长度。
每头牛参加完派对后都必须回家,无论是去参加派对还是回家,每头牛都会选择最短路径,求这nn 头牛的最短路径(一个来回)中最长的一条路径长度。
输入格式
第一行有三个整数,分别表示牛的数量 nn,道路数mm和派对农场编号 xx
接下来 mm 行,每行三个整数 uu,vv,ww表示存在一条由 uu通向 vv 的长度为 ww 的道路。
输出格式
输出一行一个整数表示答案。
输入样例
4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3
输出样例
10
说明/提示
样例 1 解释
【洛谷】P1821 [USACO07FEB] Cow Party S(单源最短路)数据规模与约定
对于全部的测试点,保证 1xn1031≤x≤n≤10^3 , 1m1051≤m≤10^51u,vn1≤u,v≤n,1w1021≤w≤10^2,保证从任何一个结点出发都能到达 xx号结点,且从 xx 出发可以到达其他所有节点。

spfa70分代码

#include<bits/stdc++.h>
       using namespace std;
       const int maxn=1e3+50;
       const int maxm=1e5+50;
       const int INF=0x3f3f3f3f;
       struct edge{
       int u;
       int v;
       int w;
       int next;
       }e1[maxm],e2[maxn];
       int head1[maxn],dis1[maxn],inq1[maxn],cnt1=0;
       int head2[maxn],dis2[maxn],inq2[maxn],cnt2=0;
       void add1(int u,int v,int w){
       cnt1++;
       e1[cnt1].u=u;
       e1[cnt1].v=v;
       e1[cnt1].w=w;
       e1[cnt1].next=head1[u];
       head1[u]=cnt1;
       }
       void add2(int u,int v,int w){
       cnt2++;
       e2[cnt2].u=u;
       e2[cnt2].v=v;
       e2[cnt2].w=w;
       e2[cnt2].next=head2[u];
       head2[u]=cnt2;
       }
       int n,m,x;
       void spfa1(int s){
       memset(dis1, INF, sizeof(dis1));
       queue<int>q;
       q.push(s);
       dis1[s]=0;
       inq1[s]=1;
       while(!q.empty()){
       int u=q.front();
       q.pop();
       inq1[u]=0;
       for(int i=head1[u];i>0;i=e1[i].next){
        int v=e1[i].v;
        int w=e1[i].w;
       if(dis1[v]>dis1[u]+w){
       dis1[v]=dis1[u]+w;
       if(!inq1[v]){
       q.push(v);
       inq1[v]=1;
       }
       }
       }
       }
       }
       void spfa2(int s){
        memset(dis2, INF, sizeof(dis2));
       queue<int>q;
       q.push(s);
       dis2[s]=0;
       inq2[s]=1;
       while(!q.empty()){
       int u=q.front();
       q.pop();
       inq2[u]=0;
       for(int i=head2[u];i>0;i=e2[i].next){
        int v=e2[i].v;
        int w=e2[i].w;
       if(dis2[v]>dis2[u]+w){
       dis2[v]=dis2[u]+w;
       if(!inq2[v]){
       q.push(v);
       inq2[v]=1;
       }
       }
       }
       }
       }
       int main(){
      // freopen("inn.txt","r",stdin);
       //freopen("outt.txt","w",stdout);
       scanf("%d%d%d",&n,&m,&x);
       for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        add1(u,v,w);
        add2(v,u,w);
        }
       spfa1(x);
       spfa2(x);
       int ans=-1;
       for(int i=1;i<=n;i++)
       ans= max(ans,dis1[i]+dis2[i]);
       printf("%d\n",ans);
        //fclose(stdin);
        //fclose(stdout);
       return 0;
       }

spfa双端队列优化70分代码

#include<bits/stdc++.h>
       using namespace std;
       const int maxn=1e3+50;
       const int maxm=1e5+50;
       const int INF=0x3f3f3f3f;
       struct edge{
       int u;
       int v;
       int w;
       int next;
       }e1[maxm],e2[maxn];
       int head1[maxn],dis1[maxn],inq1[maxn],cnt1=0;
       int head2[maxn],dis2[maxn],inq2[maxn],cnt2=0;
       void add1(int u,int v,int w){
       cnt1++;
       e1[cnt1].u=u;
       e1[cnt1].v=v;
       e1[cnt1].w=w;
       e1[cnt1].next=head1[u];
       head1[u]=cnt1;
       }
       void add2(int u,int v,int w){
       cnt2++;
       e2[cnt2].u=u;
       e2[cnt2].v=v;
       e2[cnt2].w=w;
       e2[cnt2].next=head2[u];
       head2[u]=cnt2;
       }
       int n,m,x;
       void spfa1(int s){
       memset(dis1, INF, sizeof(dis1));
       deque<int>q;
       q.push_back(s);
       dis1[s]=0;
       inq1[s]=1;
       while(!q.empty()){
       int u=q.front();
       q.pop_front();
       inq1[u]=0;
       for(int i=head1[u];i>0;i=e1[i].next){
        int v=e1[i].v;
        int w=e1[i].w;
       if(dis1[v]>dis1[u]+w){
       dis1[v]=dis1[u]+w;
       if(!inq1[v]){
       inq1[v]=1;
       if(!q.empty()&&dis1[v]<=dis1[q.front()])
       q.push_front(v);
       else q.push_back(v);
       }
       }
       }
       }
       }
       void spfa2(int s){
        memset(dis2, INF, sizeof(dis2));
       deque<int>q;
       q.push_back(s);
       dis2[s]=0;
       inq2[s]=1;
       while(!q.empty()){
       int u=q.front();
       q.pop_front();
       inq2[u]=0;
       for(int i=head2[u];i>0;i=e2[i].next){
        int v=e2[i].v;
        int w=e2[i].w;
       if(dis2[v]>dis2[u]+w){
       dis2[v]=dis2[u]+w;
       if(!inq2[v]){
       inq2[v]=1;
       if(!q.empty()&&dis1[v]<=dis1[q.front()])
       q.push_front(v);
       else q.push_back(v);
       }
       }
       }
       }
       }
       int main(){
      // freopen("inn.txt","r",stdin);
       //freopen("outt.txt","w",stdout);
       scanf("%d%d%d",&n,&m,&x);
       for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        add1(u,v,w);
        add2(v,u,w);
        }
       spfa1(x);
       spfa2(x);
       int ans=-1;
       for(int i=1;i<=n;i++)
       ans= max(ans,dis1[i]+dis2[i]);
       printf("%d\n",ans);
        //fclose(stdin);
        //fclose(stdout);
       return 0;
       }

dijkstra解法AC代码

#include<bits/stdc++.h>
       using namespace std;
       const int maxn=1e3+50;
       const int maxm=1e5+50;
       const int inf=0x3f3f3f3f;
       struct edge{
       int u;
       int v;
       int w;
       int next;
       }e1[maxm],e2[maxm];
       int head1[maxn],dis1[maxn],cnt1=0;
       int head2[maxn],dis2[maxn],cnt2=0;
       void add1(int u,int v,int w){
       cnt1++;
       e1[cnt1].u=u;
       e1[cnt1].v=v;
       e1[cnt1].w=w;
       e1[cnt1].next=head1[u];
       head1[u]=cnt1;
       }
       void add2(int u,int v,int w){
       cnt2++;
       e2[cnt2].u=u;
       e2[cnt2].v=v;
       e2[cnt2].w=w;
       e2[cnt2].next=head2[u];
       head2[u]=cnt2;
       }
       struct  node{
       int u,dis;
       bool operator<(const node& b) const{
       return dis>b.dis;
       }
	   };
       int n,m,x;
       void  disjkstra1(int s){
       for(int i=1;i<=n;i++){
       dis1[i]=inf;
       }
       priority_queue<node>que;
       dis1[s]=0;
       que.push((node){s,dis1[s]});
       while(!que.empty()){
       node now=que.top();
       que.pop();
       int  u=now.u;
       if(now.dis!=dis1[u]) continue;
       for(int i=head1[u];i>0;i=e1[i].next){
        int v=e1[i].v;
        int w=e1[i].w;
        if(dis1[v]>dis1[u]+w){
        dis1[v]=dis1[u]+w;
        que.push((node){v,dis1[v]});
        }
       }
       }
       }
       void  disjkstra2(int s){
       for(int i=1;i<=n;i++){
       dis2[i]=inf;
       }
       priority_queue<node>que;
       dis2[s]=0;
       que.push((node){s,dis2[s]});
       while(!que.empty()){
       node now=que.top();
       que.pop();
       int  u=now.u;
       if(now.dis!=dis2[u]) continue;
       for(int i=head2[u];i>0;i=e2[i].next){
        int v=e2[i].v;
        int w=e2[i].w;
        if(dis2[v]>dis2[u]+w){
        dis2[v]=dis2[u]+w;
        que.push((node){v,dis2[v]});
        }
       }
       }
       }
       int main(){
        //freopen("inn.txt","r",stdin);
        //freopen("outt.txt","w",stdout);
       scanf("%d%d%d",&n,&m,&x);
       for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        add1(u,v,w);
        add2(v,u,w);
        }
       disjkstra1(x);
       disjkstra2(x);
       int ans=-1;
       for(int i=1;i<=n;i++)
       ans= max(ans,dis1[i]+dis2[i]);
       printf("%d\n",ans);
       //fclose(stdin);
       //fclose(stdout);
       return 0;
       }