首页 > 其他 > 详细

P2149 [SDOI2009]Elaxia的路线

时间:2019-07-19 23:57:16      阅读:139      评论:0      收藏:0      [点我收藏+]

题目传送门

题目描述

最近,Elaxia和w**的关系特别好,他们很想整天在一起,但是大学的学习太紧张了,他们 必须合理地安排两个人在一起的时间。

Elaxia和w**每天都要奔波于宿舍和实验室之间,他们 希望在节约时间的前提下,一起走的时间尽可能的长。

现在已知的是Elaxia和w**所在的宿舍和实验室的编号以及学校的地图:地图上有N个路 口,M条路,经过每条路都需要一定的时间。 具体地说,就是要求无向图中,两对点间最短路的最长公共路径。

输入输出格式

输入格式:

第一行:两个整数N和M(含义如题目描述)。

第二行:四个整数x1、y1、x2、y2(1 ≤ x1 ≤ N,1 ≤ y1 ≤ N,1 ≤ x2 ≤ N,1 ≤ y2 ≤ N),分别表示Elaxia的宿舍和实验室及w**的宿舍和实验室的标号(两对点分别 x1,y1和x2,y2)。

接下来M行:每行三个整数,u、v、l(1 ≤ u ≤ N,1 ≤ v ≤ N,1 ≤ l ≤ 10000),表 u和v之间有一条路,经过这条路所需要的时间为l。

输出格式:

一行,一个整数,表示每天两人在一起的时间(即最长公共路径的长度)

输入输出样例

输入样例#1: 
9 10
1 6 7 8
1 2 1
2 5 2
2 3 3
3 4 2
3 9 5
4 5 3
4 6 4
4 7 2
5 8 1
7 9 1
输出样例#1: 
3

说明

对于30%的数据,N ≤ 100;

对于60%的数据,N ≤ 1000;

对于100%的数据,N ≤ 1500,输入数据保证没有重边和自环。


 

这题是我见过最毒瘤的题,没有之一。数组范围真的是太迷了,卡了我一天。

思路:首先当我们拿到题面时,发现出题人还是蛮友善的,直接把要求的问题写了出来。

   然后我们就要思考如何记录最短路上的路径,我们可以很容易推出,如果有一条从x到y权值为z的边。从起点1到x的最短路+从y到终点1的最短路+z如果等于从起点1到终点1的最短路并且从起点2到x的最短路+从y到终点2的最短路+z也等于从起点2到终点2的最短路,

   就说明这条边是在最短路上的。既然要求最短路的最长公共路径,我们就需要把符合条件的边重新构建出一张有向图,然后跑一边记搜。当然,最短路不止一条。要分别建两次图和记搜两次。(虽然这不符合出题人意图,但也能A)出题人可能没想到这么多


下面为大家提供两份参考代码,一份用的dijkstra堆优化求得最短路,另一份使用SPFA求最短路

 

技术分享图片
  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef pair<int,int> P;
  4 int n,m,x1,x2,yy1,y2,dis[5][50005],f[40005],next[5000005],first[10005],to[5000005],v[5000005],tot;
  5 int ans,book[10005],dp[10005],tot1,next1[5000005],first1[20005],to1[5000005],v1[5000005];
  6 void add(int x,int y,int z)
  7 {
  8     tot++;
  9     next[tot]=first[x];
 10     first[x]=tot;
 11     to[tot]=y;
 12     v[tot]=z;
 13 }
 14 void add2(int x,int y,int z)
 15 {
 16     tot1++;
 17     next1[tot1]=first1[x];
 18     first1[x]=tot1;
 19     to1[tot1]=y;
 20     v1[tot1]=z;
 21     book[x]=book[y]=1;
 22 }
 23 void dijk(int t,int num)
 24 {
 25     priority_queue<P,vector<P>,greater<P> >q;
 26     for(int i=1;i<=n;i++)  f[i]=false;
 27     dis[num][t]=0;
 28     q.push(P(0,t));
 29     while(!q.empty())
 30     {
 31         int x=q.top().second;
 32         q.pop();
 33         if(f[x]==true) continue;
 34         f[x]=true;
 35         for(int i=first[x];i;i=next[i])
 36         {
 37             int y=to[i];
 38             if(dis[num][y]>dis[num][x]+v[i])
 39             {
 40                 dis[num][y]=dis[num][x]+v[i];
 41                 q.push(P(dis[num][y],y));    
 42             } 
 43         }
 44     }
 45 }
 46 void dp1(int x)
 47 {
 48     if(dp[x]!=0) return ;
 49     for(int i=first1[x];i;i=next1[i])
 50     {
 51         int y=to1[i];
 52         dp1(y);
 53         dp[x]=max(dp[x],dp[y]+v1[i]);
 54     }
 55 }
 56 int main()
 57 {
 58     memset(dis,999999,sizeof(dis));
 59     scanf("%d %d\n%d %d %d %d",&n,&m,&x1,&yy1,&x2,&y2);
 60     for(int i=1;i<=m;i++)
 61     {
 62         int xx,yy,zz;
 63         scanf("%d %d %d",&xx,&yy,&zz);
 64         add(xx,yy,zz);
 65         add(yy,xx,zz);
 66     }
 67     dijk(x1,1);
 68     dijk(x2,2);
 69     dijk(yy1,3);
 70     dijk(y2,4);
 71     for(int i=1;i<=n;i++)
 72     {
 73         for(int j=first[i];j;j=next[j])
 74         {
 75             int y=to[j];
 76             if(dis[1][i]+dis[3][y]+v[j]==dis[1][yy1])
 77             {
 78                 if(dis[4][i]+dis[2][y]+v[j]==dis[2][y2])  add2(y,i,v[j]);
 79             }
 80         }
 81     }
 82     for(int i=1;i<=n;i++) if(!dp[i]&&book[i]) dp1(i);
 83     for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
 84     memset(dp,0,sizeof(dp));
 85     memset(first1,0,sizeof(first1));
 86     memset(next1,0,sizeof(next1));
 87     memset(to1,0,sizeof(to1));
 88     memset(v1,0,sizeof(v1));
 89     tot1=0;
 90     for(int i=1;i<=n;i++)
 91     {
 92         for(int j=first[i];j;j=next[j])
 93         {
 94             int y=to[j];
 95             if(dis[1][i]+dis[3][y]+v[j]==dis[1][yy1])
 96             {
 97                    if(dis[2][i]+dis[4][y]+v[j]==dis[2][y2])  add2(i,y,v[j]);
 98             }
 99         }
100     }
101     for(int i=1;i<=n;i++) if(!dp[i]&&book[i]) dp1(i);
102     for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
103     printf("%d",ans);
104     return 0;
105 } 
dijkstra堆优化

 

技术分享图片
  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef pair<int,int> P;
  4 int n,m,x1,x2,yy1,y2,dis[5][50005],f[40005],next[5000005],first[10005],to[5000005],v[5000005],tot;
  5 int ans,book[10005],dp[10005],tot1,next1[5000005],first1[20005],to1[5000005],v1[5000005];
  6 void add(int x,int y,int z)
  7 {
  8     tot++;
  9     next[tot]=first[x];
 10     first[x]=tot;
 11     to[tot]=y;
 12     v[tot]=z;
 13 }
 14 void add2(int x,int y,int z)
 15 {
 16     tot1++;
 17     next1[tot1]=first1[x];
 18     first1[x]=tot1;
 19     to1[tot1]=y;
 20     v1[tot1]=z;
 21     book[x]=book[y]=1;
 22 }
 23 void spfa(int t,int num)
 24 {
 25     queue<int>q;
 26     for(int i=1;i<=n;i++)  f[i]=false;
 27     dis[num][t]=0;
 28     q.push(t);
 29     f[t]=true;
 30     while(!q.empty())
 31     {
 32         int x=q.front();
 33         q.pop();
 34         f[x]=false;
 35         for(int i=first[x];i;i=next[i])
 36         {
 37             int y=to[i];
 38             if(dis[num][y]>dis[num][x]+v[i])
 39             {
 40                 dis[num][y]=dis[num][x]+v[i];
 41                 if(f[y]==false)
 42                 {
 43                     q.push(y);
 44                     f[y]=true;
 45                 }
 46                     
 47             } 
 48         }
 49     }
 50 }
 51 void dp1(int x)
 52 {
 53     if(dp[x]!=0) return ;
 54     for(int i=first1[x];i;i=next1[i])
 55     {
 56         int y=to1[i];
 57         dp1(y);
 58         dp[x]=max(dp[x],dp[y]+v1[i]);
 59     }
 60 }
 61 int main()
 62 {
 63     memset(dis,999999,sizeof(dis));
 64     scanf("%d %d\n%d %d %d %d",&n,&m,&x1,&yy1,&x2,&y2);
 65     for(int i=1;i<=m;i++)
 66     {
 67         int xx,yy,zz;
 68         scanf("%d %d %d",&xx,&yy,&zz);
 69         add(xx,yy,zz);
 70         add(yy,xx,zz);
 71     }
 72     spfa(x1,1);
 73     spfa(x2,2);
 74     spfa(yy1,3);
 75     spfa(y2,4);
 76     for(int i=1;i<=n;i++)
 77     {
 78         for(int j=first[i];j;j=next[j])
 79         {
 80             int y=to[j];
 81             if(dis[1][i]+dis[3][y]+v[j]==dis[1][yy1])
 82             {
 83                 if(dis[4][i]+dis[2][y]+v[j]==dis[2][y2])  add2(y,i,v[j]);
 84             }
 85         }
 86     }
 87     for(int i=1;i<=n;i++) if(!dp[i]&&book[i]) dp1(i);
 88     for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
 89     memset(dp,0,sizeof(dp));
 90     memset(first1,0,sizeof(first1));
 91     memset(next1,0,sizeof(next1));
 92     memset(to1,0,sizeof(to1));
 93     memset(v1,0,sizeof(v1));
 94     tot1=0;
 95     for(int i=1;i<=n;i++)
 96     {
 97         for(int j=first[i];j;j=next[j])
 98         {
 99             int y=to[j];
100             if(dis[1][i]+dis[3][y]+v[j]==dis[1][yy1])
101             {
102                    if(dis[2][i]+dis[4][y]+v[j]==dis[2][y2])  add2(i,y,v[j]);
103             }
104         }
105     }
106     for(int i=1;i<=n;i++) if(!dp[i]&&book[i]) dp1(i);
107     for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
108     printf("%d",ans);
109     return 0;
110 } 
SPFA

 

P2149 [SDOI2009]Elaxia的路线

原文:https://www.cnblogs.com/jiuduSHENBENG/p/11216054.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!