Route Change

The road system of a country connects all N cities so that it is possible to travel between any pair of cities using existing roads. Each road connects two different cities, is two-way and one has exactly one toll booth (a toll is paid for both directions of traffic). Roads intersect only in a city and no pair of cities is interconnected by two or more roads.

Dias Tranport offers a one-day parcel delivery service between cities. Each parcel must be transported from a city A to another city B. The management of Dias Transport defines, for each parcel, a service route, consisting of C cities and C - 1 roads: the first city on the service route is the origin of the parcel, the final city is the destination of the parcel. The service route never passes twice through the same city, and the vehicle chosen to deliver a parcel can only travel by the service route defined.

One day, however, a vehicle broke down and was taken for repairs in a city that was not among the cities in its service route. The management of Dias Transport wants to know which is the lowest total cost, in terms of tolls, for delivering the parcel (that is, to take the vehicle from the city it was repaired to the destination city), but with an additional constraint: if at some point the vehicle reaches one of the cities that make up its service route, it should go back to following its service route.

Input 

The input contains several test cases. The first line of a test case contais four integers N, M, C and K ( 4N250, 3MN x (N - 1)/2, 2CN - 1 e CKN - 1), representing, respectively, the number of cities, the number of roads, the number of cities in the service route and the city where the vehicle was taken for repair. The cities are identified by integers from 0 to N - 1. The service route is 0, 1,..., C - 1, that is, the origin is 0, from 0 goes to 1, from 1 to 2 and so on, until the destination C - 1. The next M lines describe the road system. Each of those lines describes one road and contains three integers U, V and P (0U, VN - 1, UV , 0P250), indicating that there exists a road connecting cities U and V with a toll of cost P.

The last test case is followed by a line containing four zeros separated by blank spaces.

Output 

For each test case, your program should print a single line, containing a single integer, the minimum total toll cost for the vehicle to reach the destination city.

Sample Input 

4 6 3 3
0 1 10
1 2 10
0 2 1
3 0 1
3 1 10
3 2 10
6 7 2 5
5 2 1
2 1 10
1 0 1
3 0 2
3 4 2
3 5 3
5 4 2
5 5 2 4
0 1 1
1 2 2
2 3 3
3 4 4
4 0 5
0 0 0 0

Sample Output 

10
6
6

---

題目描述：

內有一條服務線呈現鍊狀 1-2-3-...-C，而現在車子被送到 N，而現在車子要回到終點 C，假如車子經過 1~C 其中一個，則必須遵循鍊狀抵達 C，求最少花費。

題目解法：

為了符合題目條件，則把 1~C 這個幾個點，直接做出 1-C 的距離，2-C 的距離 ... 等。

而當存在於非服務線上的點時，則單向讓它指 1~C。防止再次脫離服務線。

建圖的時候特別小心即可。

#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct E {
    int to, cost;
    E(int a, int b):
        to(a), cost(b) {}
};
vector<E> g[255];
void spfa(int st, int ed) {
    int dist[255] = {}, inq[255] = {};
    int i, tn;
    queue<int> Q;
    memset(dist, 63, sizeof(dist));
    dist[st] = 0;
    Q.push(st);
    while(!Q.empty()) {
        tn = Q.front();
        Q.pop(), inq[tn] = 0;
        for(i = 0; i < g[tn].size(); i++) {
            if(dist[g[tn][i].to] > dist[tn]+g[tn][i].cost) {
                dist[g[tn][i].to] = dist[tn]+g[tn][i].cost;
                if(inq[g[tn][i].to] == 0) {
                    inq[g[tn][i].to] = 1;
                    Q.push(g[tn][i].to);
                }
            }
        }
    }
    printf("%d\n", dist[ed]);
}
int main() {
    int n, m, c, k;
    int x, y, cc;
    int i, j;
    while(scanf("%d %d %d %d", &n, &m, &c, &k) == 4 && n) {
        for(i = 0; i < n; i++)
            g[i].clear();
        int nt[255] = {};
        while(m--) {
            scanf("%d %d %d", &x, &y, &cc);
            if(x >= c && y >= c) {
                g[x].push_back(E(y, cc));
                g[y].push_back(E(x, cc));
            } else if(x < c && y >= c) {
                g[y].push_back(E(x, cc));
            } else if(x >= c && y < c) {
                g[x].push_back(E(y, cc));
            } else {
                if(x > y)   swap(x, y);
                if(x+1 == y)
                    nt[x] = cc;
            }
        }
        int sum = 0;
        for(i = c-2; i >= 0; i--) {
            sum += nt[i];
            g[i].push_back(E(c-1, sum));
        }
        spfa(k, c-1);
    }
    return 0;
}

---