2014
11-29

Shortest Path

When YY was a boy and LMY was a girl, they trained for NOI (National Olympiad in Informatics) in GD team. One day, GD team’s coach, Prof. GUO asked them to solve the following shortest-path problem.
There is a weighted directed multigraph G. And there are following two operations for the weighted directed multigraph:
(1) Mark a vertex in the graph.
(2) Find the shortest-path between two vertices only through marked vertices.
For it was the first time that LMY faced such a problem, she was very nervous. At this moment, YY decided to help LMY to analyze the shortest-path problem. With the help of YY, LMY solved the problem at once, admiring YY very much. Since then, when LMY meets problems, she always calls YY to analyze the problems for her. Of course, YY is very glad to help LMY. Finally, it is known to us all, YY and LMY become programming lovers.
Could you also solve the shortest-path problem?

The input consists of multiple test cases. For each test case, the first line contains three integers N, M and Q, where N is the number of vertices in the given graph, N≤300; M is the number of arcs, M≤100000; and Q is the number of operations, Q ≤100000. All vertices are number as 0, 1, 2, … , N – 1, respectively. Initially all vertices are unmarked. Each of the next M lines describes an arc by three integers (x, y, c): initial vertex (x), terminal vertex (y), and the weight of the arc (c). (c > 0) Then each of the next Q lines describes an operation, where operation “0 x” represents that vertex x is marked, and operation “1 x y” finds the length of shortest-path between x and y only through marked vertices. There is a blank line between two consecutive test cases.
End of input is indicated by a line containing N = M = Q = 0.

The input consists of multiple test cases. For each test case, the first line contains three integers N, M and Q, where N is the number of vertices in the given graph, N≤300; M is the number of arcs, M≤100000; and Q is the number of operations, Q ≤100000. All vertices are number as 0, 1, 2, … , N – 1, respectively. Initially all vertices are unmarked. Each of the next M lines describes an arc by three integers (x, y, c): initial vertex (x), terminal vertex (y), and the weight of the arc (c). (c > 0) Then each of the next Q lines describes an operation, where operation “0 x” represents that vertex x is marked, and operation “1 x y” finds the length of shortest-path between x and y only through marked vertices. There is a blank line between two consecutive test cases.
End of input is indicated by a line containing N = M = Q = 0.

5 10 10
1 2 6335
0 4 5725
3 3 6963
4 0 8146
1 2 9962
1 0 1943
2 1 2392
4 2 154
2 2 7422
1 3 9896
0 1
0 3
0 2
0 4
0 4
0 1
1 3 3
1 1 1
0 3
0 4
0 0 0

Case 1:
ERROR! At point 4
ERROR! At point 1
0
0
ERROR! At point 3
ERROR! At point 4

1 题目给的n <= 300，而边数m<=100000，并且有Q<= 100000次询问。刚开始我用优先队列+Dij然后就开始TLE，然后就没然后了。
2 看了题解之后猛然发现这尼玛就是floyd,（对算法理解不透测）。我们知道floyd就是每次都拿一个中间点k来更新dis，题目中是只有标记过的点才能够使用，那么就像floyd一样只要是标记来这个点那么就可以用这个点来进行更新dis，然后如果要求两点直间的距离只要查找即可。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;

#define MAXN 310
#define INF 0xFFFFFFF

int n , m , Q , cnt , flag;
int vis[MAXN];
int weight[MAXN][MAXN];

void init(){
for(int i = 0 ; i < n ; i++){
vis[i] = 0;
for(int j = 0 ; j < n ; j++)
weight[i][j] = INF;
weight[i][i] = 0;
}
}

int min(int a , int b){
return a < b ? a : b;
}

void floyd(int s){
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < n ; j++)
weight[i][j] = min(weight[i][s]+weight[s][j] , weight[i][j]);
}
}

int main(){
int x , s , e , v;
cnt = 1;
flag = 1;
while(scanf("%d%d%d" , &n , &m , &Q) && n+m+Q){
init();
for(int i = 0 ; i < m ; i++){
scanf("%d%d%d" , &s , &e , &v);
if(weight[s][e] > v)
weight[s][e] = v;
}
if(!flag)
printf("\n");
else
flag = 0;
printf("Case %d:\n" , cnt++);
for(int i = 0 ; i < Q ; i++){
scanf("%d" , &x);
if(!x){
scanf("%d" , &s);
if(!vis[s]){
vis[s] = 1;
floyd(s);/*更新dis*/
}
else
printf("ERROR! At point %d\n" , s);
}
else{
scanf("%d%d" , &s , &e);
if(!vis[s] || !vis[e])
printf("ERROR! At path %d to %d\n" , s , e);
else{
if(weight[s][e] == INF)
printf("No such path\n");
else
printf("%d\n" , weight[s][e]);
}
}
}
}
return 0;
}