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

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;
}

我要檢舉

#10525#New to Bangladesh

台長： Morris

您可能對以下文章有興趣

[UVA][dp] 672 - Gangsters

[UVA][JAVA] 10023 - Square root

[UVA][bitmap、搜索、博弈] 322 - Ships

[UVA][數學] 10830 - A New Function

人氣(471) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][五則運算] 10932 - Calculator
此分類上一篇:[UVA][時間計算] 10339 - Watching Watches

回應(0)