[UVA][最短路] 10525 - New to Bangladesh
THE SAMS' CONTEST
Problem 6
BACKGROUND
Mr. Tonmoy is a service holder of BUET ( British Ultramodern Energy Technique ) Company. He liked his boss very much. But, recently, he hates him as he (The Boss) ordered him to go to Bangladesh. Tonmoy knows that Bangladesh is a country of Traffic Jam and no Government has yet taken this serious problem into account. All the people of that country matched themselves with this annoying Jam. At first, Tonmoy wanted to avoid the order but the boss insisted him visiting Bangladesh. Well, as there is no way to escape, Tonmoy is planning to take the Laptop and a map of roads of Bangladesh with him. Now your task is to help Tonmoy by writing a good program that will take different roadmaps of Bangladesh and help him to determine the shortest road having shortest time ( first considering shortest time then shortest road among the determined paths ) to go from one place to another so that he can avoid that terrible jam.
Input
Input consists of several input blocks. The first line in the input file consists of the number of cases to solve. Next lines will consist of several roadmaps. The first line of a block consists two integers x & y indicating the number of distinct places and the number of roads exists between them. Places are numbered starting from 1. The next y lines consists of four integers a, b, c, d indicating two ends of a road, time and road length respectively. Next line contains number of queries q for that particular map. Next q lines contains two integers, source and destination. You are to compute shortest distance having shortest time from the source to destination for each query. None of the roads of Bangladesh are one ways. Consecutive blocks are separated by a blank line. There are at most 25 roads in a road map.
Output
For each query your correct program should output one of the two cases , in a separate line.
1) No Path.
2) Distance and time to reach destination is m & n.
where m and n indicate distance and time to reach from source to destination respectively using the above process. Consecutive blocks of outputs should be separated by a blank line. For clarification check the following sample inputs and corresponding outputs.
Sample Input
2 3 2 1 2 2 5 2 3 3 6 2 1 3 1 3 4 2 1 2 5 2 2 3 6 3 1 1 4
Sample Output
Distance and time to reach destination is 11 & 5. Distance and time to reach destination is 11 & 5. No Path.
Anupam & Shabuj ( BUET PESSIMISTIC )
題目會給一條路的長度跟花費時間。
要求起點到終點的最小花費時間與長度。
求最小花費時間下的最短距離。
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
struct E {
int to, ct, cl;
E(int a, int b, int c):
to(a), ct(b), cl(c) {}
};
vector<E> g[55];
void spfa(int st, int ed) {
int tn, i, j, k;
int dist[55][2];//[0] length, [1] time
int inq[55] = {};
memset(dist, 63, sizeof(dist));
int oo = dist[0][0];
dist[st][0] = dist[st][1] = 0;
queue<int> Q;
Q.push(st);
while(!Q.empty()) {
tn = Q.front(), Q.pop();
inq[tn] = 0;
if(dist[tn][1] > dist[ed][1])
continue;
for(vector<E>::iterator it = g[tn].begin();
it != g[tn].end(); it++) {
if(dist[it->to][1] > dist[tn][1] + it->ct ||
(dist[it->to][1] == dist[tn][1] + it->ct &&
dist[it->to][0] > dist[tn][0] + it->cl)) {
dist[it->to][0] = dist[tn][0] + it->cl;
dist[it->to][1] = dist[tn][1] + it->ct;
if(inq[it->to] == 0) {
inq[it->to] = 1;
Q.push(it->to);
}
}
}
}
if(dist[ed][0] == oo)
puts("No Path.");
else
printf("Distance and time to reach destination is %d & %d.\n", dist[ed][0], dist[ed][1]);
}
int main() {
int testcase;
int x, y, ct, cl;
int i, j;
scanf("%d", &testcase);
while(testcase--) {
int n, m;
scanf("%d %d", &n, &m);
for(i = 1; i <= n; i++)
g[i].clear();
while(m--) {
scanf("%d %d %d %d", &x, &y, &ct, &cl);
g[x].push_back(E(y, ct, cl));
g[y].push_back(E(x, ct, cl));
}
scanf("%d", &m);
while(m--) {
scanf("%d %d", &x, &y);
spfa(x, y);
}
if(testcase)
puts("");
}
return 0;
}