Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

We have n cities that are connected by m bi-direction roads. Each city has a unique id from 1 to n, so we have cities c₁,..., c_n. Let r_ij be the road connecting two cities c_i and c_j, then r_ij has a length l_ij and condition d_ij, where the length is a positive integer and the condition is an integer from 1 to k. Note that all roads are bidirectional so l_ij is equal to l_ji and d_ij is the same as d_ji.

We want to drive a car from a starting city c_s to a destination city c_d along a shortest route. However, the condition of a road has a severe impact on the suspension system of our car. That is, after driving through a road of condition c, we cannot drive through another road of condition c immediately, otherwise the suspension of our car will break down. For example, if road r₁₂ has condition 1 and r₂₃ also has condition 1, then we cannot drive from c₁ to c₂ to c₃. However, if road r₁₂ has condition 1, r₂₃ has condition 2, and r₃₄ also has condition 1, then we can drive from c₁ to c₂ to c₃ to c₄, since we did not drive through two roads of the same condition consecutively.

Now given the condition and length of all roads and p pairs of starting and destination city pairs, please compute the shortest path for each pair of cities without going through two consecutive roads of the same condition.

Technical Specifications

1. The number of cities n is no more than 50.
2. The number of roads m is no more than 500.
3. The number of conditions k is no more than 50.
4. The number of source and destination city pairs p is no more than 15.
5. The length of each l_ij is at most 2¹⁵.

Input 

The first line of the input file contains an integer, denoting the number of test cases to follow. The first line of each test case has the number of cities n, the number of roads m, the number of conditions k, and the number of city pairs p to compute the distance. Each of the next m lines has the information of a road, including the ids of the starting city i and the destination city j, the distance l_ij and the condition d_ij. To simplify the input presentation we also assume that i < j so that a road will appear exactly once in the input. Each of the next p lines has the source and destination city pairs to compute the distance.

Output 

For each test case, output the length of the shortest route from the starting city to the destination city without going through two consecutive roads of the same condition for the p city pairs. If there are no feasible routes between a pair of cities, please output ``infinity''.

Sample Input 

2
5 5 3 5
1 2 1 1
2 3 100 2
3 4 100 3
4 5 1 1
2 4 1 2
1 4
1 5
2 4
2 5
3 5
5 5 2 5
1 2 1 1
2 3 100 2
3 4 100 2
4 5 500 1
2 4 1 1
1 4
1 5
2 4
2 5
3 5

Sample Output 

2
3
1
2
101
infinity
infinity
1
infinity
600

---

不能走跟上一次一樣條件的道路, 因為僅只有上一次, 因此在記錄最短路徑的時候,
狀態 [節點][條件], 去做更新, 只要不重疊就可以繼續更新, 直到找到最佳解

#include <iostream>
#include <cstdio>
#include <cstdlib>
#define oo 100000000
using namespace std;
typedef struct {
    int x, y, l, k;
}Path;
Path Map[1001];
int cmp(const void *i, const void *j) {
    Path *x, *y;
    x = (Path *)i, y = (Path *)j;
    return x->x - y->x;
}
int min(int x, int y) {
    return x < y ? x : y;
}
int NodeL[51], NodeT[51];
int Queue[10000000];
void SPFA(int st, int ed, int n, int kind) {
    int i, j, k, l, Qt;
    int V[51][51], Cut = oo;
    for(i = 1; i <= n; i++)
        for(j = 0; j <= kind; j++)
            V[i][j] = oo;
    V[st][0] = 0, Queue[0] = st, Qt = 0;
    for(i = 0; i <= Qt; i++) {
        int tn = Queue[i];
        for(j = 0, k = NodeL[tn]; j < NodeT[tn]; j++, k++) {
            for(l = 0; l <= kind; l++)
                if(l != Map[k].k) {
                    if(V[Map[k].y][Map[k].k] > V[tn][l] + Map[k].l) {
                        V[Map[k].y][Map[k].k] = V[tn][l] + Map[k].l;
                        if(V[Map[k].y][Map[k].k] <= Cut)
                            Queue[++Qt] = Map[k].y;
                        if(Map[k].y == ed)
                            Cut = min(Cut, V[Map[k].y][Map[k].k]);
                    }
                }
        }
    }
    int Min = oo;
    for(i = 0; i <= kind; i++)
        Min = min(Min, V[ed][i]);
    if(Min == oo)
        printf("infinity\n");
    else
        printf("%d\n", Min);
}
int main() {
    int T, i, n, m, k, p;
    scanf("%d", &T);
    while(T--) {
        scanf("%d %d %d %d", &n, &m, &k, &p);
        for(i = 1; i <= n; i++)
            NodeL[i] = oo, NodeT[i] = 0;
        for(i = 0; i < m; i++) {
            scanf("%d %d %d %d", &Map[i].x, &Map[i].y, &Map[i].l, &Map[i].k);
            Map[i+m].x = Map[i].y;
            Map[i+m].y = Map[i].x;
            Map[i+m].l = Map[i].l;
            Map[i+m].k = Map[i].k;
        }
        m *= 2;
        qsort(Map, m, sizeof(Path), cmp);
        int st, ed;
        for(i = 0; i < m; i++) {
            NodeL[Map[i].x] = min(NodeL[Map[i].x], i);
            NodeT[Map[i].x]++;
        }
        while(p--) {
            scanf("%d %d", &st, &ed);
            SPFA(st, ed, n, k);
        }
    }
    return 0;
}