10.26T4 最短路+拓扑排序最长路

3883 -- 【SDOI2009】Elaxia的路线

Description

　　最近，Elaxia和w**的关系特别好，他们很想整天在一起，但是大学的学习太紧张了，他们必须合理地安排两个人在一起的时间。Elaxia和w**每天都要奔波于宿舍和实验室之间，他们希望在节约时间的前提下，一起走的时间尽可能的长。
　　现在已知的是Elaxia和w**所在的宿舍和实验室的编号以及学校的地图：地图上有N个路口，M条路，经过每条路都需要一定的时间。
　　具体地说，就是要求无向图中，两对点间最短路的最长公共路径。

Input

　　第一行：两个整数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。

Output

一行，一个整数，表示每天两人在一起的时间（即最长公共路径的长度）。

Sample Input

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

Sample Output

Hint

【数据范围】
　　对于30%的数据，N≤100；
　　对于60%的数据，N≤1000；
　　对于100%的数据，N≤1500，输入数据保证没有重边和自环。

Source

xinyue

首先从四个点跑最短路，看哪一些边在两个的最短路上面，重新建一个图，然后我们就可以在这个DAG上面跑最短路了

code：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<queue>
  4 #include<cstring>
  5 #define N 1000006
  6 using namespace std;
  7 struct node {
  8     int u,v,w;
  9 } e[N],e1[N];
 10 int first[N],nxt[N],cnt;
 11 void add(int u,int v,int w) {
 12     e[++cnt].u=u;
 13     e[cnt].v=v;
 14     e[cnt].w=w;
 15     nxt[cnt]=first[u];
 16     first[u]=cnt;
 17 }
 18 int first1[N],nxt1[N],cnt1;
 19 int x1,y1,x2,y2;
 20 void add2(int u,int v,int w) {
 21     e1[++cnt1].u=u;
 22     e1[cnt1].v=v;
 23     e1[cnt1].w=w;
 24     nxt1[cnt1]=first1[u];
 25     first1[u]=cnt1;
 26 }
 27 int dis1[N],dis2[N],dis3[N],dis4[N],dis[N],vis[N];
 28 void spfa1() {
 29     queue<int>q;
 30     memset(dis1,0x3f3f3f3f,sizeof dis1);
 31     memset(vis,0,sizeof vis);
 32     vis[x1]=1;
 33     dis1[x1]=0;
 34     q.push(x1);
 35     while(!q.empty()) {
 36         int u=q.front();
 37         q.pop();
 38         vis[u]=0;
 39         for(int i=first[u]; i; i=nxt[i]) {
 40             int v=e[i].v;
 41             if(dis1[v]>dis1[u]+e[i].w) {
 42                 dis1[v]=dis1[u]+e[i].w;
 43                 if(!vis[v]) {
 44                     vis[v]=1;
 45                     q.push(v);
 46                 }
 47             }
 48         }
 49     }
 50 }
 51 void spfa2() {
 52     queue<int>q;
 53     memset(dis2,0x3f3f3f3f,sizeof dis2);
 54     memset(vis,0,sizeof vis);
 55     vis[x2]=1;
 56     dis2[x2]=0;
 57     q.push(x2);
 58     while(!q.empty()) {
 59         int u=q.front();
 60         q.pop();
 61         vis[u]=0;
 62         for(int i=first[u]; i; i=nxt[i]) {
 63             int v=e[i].v;
 64             if(dis2[v]>dis2[u]+e[i].w) {
 65                 dis2[v]=dis2[u]+e[i].w;
 66                 if(!vis[v]) {
 67                     vis[v]=1;
 68                     q.push(v);
 69                 }
 70             }
 71         }
 72     }
 73 }
 74 void spfa3() {
 75     queue<int>q;
 76     memset(dis3,0x3f3f3f3f,sizeof dis3);
 77     memset(vis,0,sizeof vis);
 78     vis[y1]=1;
 79     dis3[y1]=0;
 80     q.push(y1);
 81     while(!q.empty()) {
 82         int u=q.front();
 83         q.pop();
 84         vis[u]=0;
 85         for(int i=first[u]; i; i=nxt[i]) {
 86             int v=e[i].v;
 87             if(dis3[v]>dis3[u]+e[i].w) {
 88                 dis3[v]=dis3[u]+e[i].w;
 89                 if(!vis[v]) {
 90                     vis[v]=1;
 91                     q.push(v);
 92                 }
 93             }
 94         }
 95     }
 96 }
 97 void spfa4() {
 98     queue<int>q;
 99     memset(dis4,0x3f3f3f3f,sizeof dis4);
100     memset(vis,0,sizeof vis);
101     vis[y2]=1;
102     dis4[y2]=0;
103     q.push(y2);
104     while(!q.empty()) {
105         int u=q.front();
106         q.pop();
107         vis[u]=0;
108         for(int i=first[u]; i; i=nxt[i]) {
109             int v=e[i].v;
110             if(dis4[v]>dis4[u]+e[i].w) {
111                 dis4[v]=dis4[u]+e[i].w;
112                 if(!vis[v]) {
113                     vis[v]=1;
114                     q.push(v);
115                 }
116             }
117         }
118     }
119 }
120 int ru[N];
121 int n,m;
122 int topsort() {
123     queue<int>q;
124     for(int i=1; i<=n; i++)if(!ru[i])q.push(i);
125     while(!q.empty()) {
126         int u=q.front();
127         q.pop();
128         for(int i=first1[u]; i; i=nxt1[i]) {
129             int v=e1[i].v;
130             dis[v]=max(dis[v],dis[u]+e1[i].w);
131             ru[v]--;
132             if(!ru[v])q.push(v);
133         }
134     }
135     int max0=0;
136     for(int i=1; i<=n; i++)max0=max(dis[i],max0);
137     return max0;
138 }
139 int a[N],b[N],c[N];
140 int main() {
141     cin>>n>>m;
142     cin>>x1>>y1>>x2>>y2;
143     for(int i=1; i<=m; i++) {
144         cin>>a[i]>>b[i]>>c[i];
145         add(a[i],b[i],c[i]);
146         add(b[i],a[i],c[i]);
147     }
148     spfa1();
149     spfa2();
150     spfa3();
151     spfa4();
152 //    for(int i=1;i<=n;i++)cout<<dis4[i]<<" ";
153 //    cout<<'
';
154     int shortest1=dis1[y1],shortest2=dis2[y2];
155 //    cout<<shortest1<<" ||| "<<shortest2<<'
';
156     for(int i=1; i<=cnt; i++) {
157         int u=e[i].u,v=e[i].v,w=e[i].w;
158         if((dis1[u]+dis3[v]+w==shortest1&&dis2[u]+dis4[v]+w==shortest2)||(dis1[u]+dis3[v]+w==shortest1&&dis2[v]+dis4[u]+w==shortest2)) {
159             add2(u,v,w);
160             ru[v]++;
161 //            cout<<u<<" "<<v<<" "<<w<<'
';
162         }
163     }
164     cout<<topsort();
165     return 0;
166 }

over