Route Change

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 

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

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