[[problem:AVOID]]

플로이드 알고리즘으로, 임의의 노드에 대해 시작점-노드, 노드-끝점의 최단거리를 구할 수 있고, (시작점-노드 최단거리 + 노드-끝점 최단거리 = 시작점 - 끝점 최단거리) 인지를 판별하여 임의의 노드가 최단거리의 일부인지 확인할 수 있습니다. 이후, 시작점에서의 거리 순으로 정렬하여 노드를 하나씩 살피며, 각 노드에서 인접한 노드 중 최단거리에 속하는 노드에 확률을 뿌려주는 형태로 해결했습니다. 클래스 E는 간선을 의미하고, 클래스 F는 분수의 표현을 의미합니다.
이 상태에서 저지에 제출하면, 분수의 분모가 분자보다 크다는 부분에서 assertion failure 가 뜹니다. 어느 부분에 오류가 있는걸까요?

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <climits>

using namespace std;

class F
{
public:
    long long numer;
    long long denom;
    F(long long a, long long b)
    {
        numer = a;
        denom = b;
        yakbun();
    }
    
    static F myAdd(F A, F B)
    {
        return F(A.numer * B.denom + A.denom * B.numer, A.denom * B.denom);
    }
    
    void myAdd(F A)
    {
        *this = F::myAdd(A, *this);
    }
    
    static long long gcd(long long a, long long b) // a < b
    {
        if(a == 0)
            return b;
        else
            return gcd(b%a, a);
    }
    
    void yakbun()
    {
        assert(numer <= denom); //here
        long long gcd = F::gcd(numer, denom);
        numer /= gcd;
        denom /= gcd;
    }
    
    F myDiv(long long a)
    {
        return F(numer, denom * a);
    }
    
};

class E
{
public:
    int from, to, val;
    E(int a, int b, int c)
    {
        from = a;
        to = b;
        val = c;
    }
    bool friend operator < (E A, E B)
    {
        return A.val < B.val;
    }
     
};

void solve();

int main()
{
    int T;
    cin >> T;
    while(T--)
        solve();
}

void solve()
{
    int N, M, targetSize;
    vector <int> target;
    vector <vector <E> > A;
    vector <vector <int> > B;
    
    cin >> N >> M >> targetSize;
    A.resize(N);
    B.resize(N);
    
    for(int i=0; i<M; i++)
    {
        int temp1, temp2, temp3;
        scanf("%d%d%d", &temp1, &temp2, &temp3);
        A[temp1-1].push_back(E(temp1-1, temp2-1, temp3));
        A[temp2-1].push_back(E(temp2-1, temp1-1, temp3));
    }
    for(int i=0; i<targetSize; i++)
    {
        int temp;
        cin >> temp;
        target.push_back(temp-1);
    }
    
//floyd algorithm
    int D[N][N][N+1];
    
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            for(int k=0; k<=N; k++)
                D[i][j][k] = INT_MAX/2 - 1;//-1;

    for(int i=0; i<N; i++)
        D[i][i][0] = 0;
    for(int i=0; i<N; i++)
        for(int j=0; j<A[i].size(); j++)
            D[A[i][j].from][A[i][j].to][0] = A[i][j].val;
    
    for(int k=0; k<N; k++)
        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++)
                D[i][j][k+1] = min(D[i][k][k] + D[k][j][k], D[i][j][k]);
    
//sort by distance from the starting vertex, and calculate probabillity in each vertex
    vector <E> G;
    for(int i=0; i<N; i++)
        G.push_back(E(i,i,D[0][i][N]));
    sort(G.begin(), G.end());
    vector <F> FR;
    FR.push_back(F(1,1));
    for(int i=1; i<N; i++)
        FR.push_back(F(0,1));
    
    for(int i=0; i<N; i++)
    {
        int current = G[i].from;
        if(D[0][current][N] + D[current][N-1][N] != D[0][N-1][N])
            continue;
        vector <int> spread;
        spread.clear();
        for(int j=0; j<A[current].size(); j++)
            if(A[current][j].val + D[A[current][j].to][N-1][N] == D[current][N-1][N])
//            if(D[current][A[current][j].to][N] + D[A[current][j].to][N-1][N] == D[current][N-1][N])
                spread.push_back(A[current][j].to);
        if(spread.empty()) continue;
        FR[current] = FR[current].myDiv((long long)spread.size());
        for(int j=0; j<spread.size(); j++)
            FR[spread[j]].myAdd(FR[current]);
    }
    
    for(int i=0; i<targetSize; i++)
        printf("%llu/%llu\n", FR[target[i]].numer, FR[target[i]].denom);
}