algospot.com

후.. 맞는거 같은데 틀리니 어렵네요.. 인풋이 복잡해서 반례 찾기도 힘들구요 ㅠ.ㅠ
아.. 어디가 틀렸는지 좀 봐주실수 있으신가요?

다익스트라로 돌리면서 이전 index값 찾고 그걸 가지고 카운팅했는데.. WA가 나오네요.

한번 어디가 틀렸는지 찾아봐주실수 있으신가요? ㅠ.ㅠ
부탁드립니다;;

#include 

#include 

#include 

#include 

#include 



#define MAX 101

#define INT_MAX 9999999



using namespace std;



int V;

int E;

int N;



int g[MAX][MAX];

int in[MAX];

int cost[MAX];

set indexes[MAX];



int cnt[MAX];



priority_queue, vector >, greater > > que;



int gcd(int m, int n)

{

	while (n != 0)

	{

		int r = m % n;

		m = n;

		n = r;

	}



	return m;

}



int calcCnt(int n)

{

	int temp = 0;

	if ( indexes[n].size() > 0 )

	{

		for (set::iterator it = indexes[n].begin(); it != indexes[n].end(); it ++)

		{

			temp += calcCnt(*it);

		}

	}

	else

	{

		temp = 1;

	}

	

	cnt[n] += temp;

	

	return temp;

}



void solve()

{

	memset(cnt, 0, sizeof(cnt));

	for(int i = 0; i <= N; i ++)<br />
	{

		indexes[i].clear();

	}



	for(int i = 0; i <= V; i ++)<br />
	{

		cost[i] = INT_MAX;

	}



	que.push(make_pair(0, 1));

	while (!que.empty())

	{

		pair now = que.top();

		que.pop();



		if ( cost[now.second] < now.first )

		{

			continue;

		}



		for ( int i = 1; i <= V; i ++)<br />
		{

			if (g[now.second][i] != 0)

			{

				int temp = now.first + g[now.second][i];

				

				if (cost[i] >= temp)

				{

					cost[i] = temp;



					que.push(make_pair(temp, i));

					indexes[i].insert(now.second);

				}

			}

		}

	}



	calcCnt(V);



	for (int i = 0; i < N; i ++)

	{

		int gcdValue = gcd(cnt[V], cnt[in[i]]);

		printf("%d/%d\n", cnt[in[i]]/gcdValue, cnt[V]/gcdValue);

	}

}



int main()

{

	int c;

	scanf("%d", &c);

	while (c--)

	{

		scanf("%d %d %d", &V, &E, &N);



		memset(g, 0, sizeof(g));

		for (int i = 0; i < E; i ++)

		{

			int s, t, v;

			scanf("%d %d %d", &s, &t, &v);



			g[s][t] = v;

		}



		for (int i = 0; i < N; i ++)

		{

			scanf("%d", &in[i]);

		}



		solve();

	}



	return 0;

}