계속 오답이 뜨네요...
제가 한 방법은
1. 다익스트라 알고리즘으로 각 노드 별로 최단거리를 구한다.
2. 최단거리 정보를 이용해 재귀를 돌려서 1번 노드로부터 i번노드까지 최단거리 경로 갯수와 V번 노드로부터 i번 노드까지 최단거리 경로 갯수를 각각 d2, d1에 저장한다.
3. i번 노드를 지나가는 경로 개수는 d1[i-1]*d2[i-1]이고, 총 최단거리 경로 갯수는 d10이다. 기약분수로 바꿔서 출력한다.
알고리즘에 이상이 있나요?

~~~ c++
#include
#include
#include
#include

#define INF 987654321

using namespace std;

vector>> G;
priority_queue,vector>,greater>> Q;

const int MAX=111;

int dist[MAX];

int dfs1(int index,int *d1)
{
//메모이제이션
if(d1[index]!=-1)
return d1[index];
int s=0;
for(int i=0;i<G[index].size();i++)
// 현재 노드까지의 최단거리랑, 인접한 노드의 최단거리+인접한노드에서 현재 노드 사이의 거리가 같으면 최단경로에 포함되는 길이다. 재귀호출하여 경우의 수에 더해준다.
if(dist[G[index][i].second]==dist[index]+G[index][i].first)
s+=dfs1(G[index][i].second,d1);
d1[index]=s;
return s;
}

int dfs2(int index,int *d2)
{
if(d2[index]!=-1)
return d2[index];
int s=0;
for(int i=0;i<G[index].size();i++)
if(dist[G[index][i].second]==dist[index]-G[index][i].first)
s+=dfs2(G[index][i].second,d2);
d2[index]=s;
return s;
}

int gcd(int a,int b)
{
if(a==0)
return b;
return gcd(b%a,a);
}

int main()
{
int c;
scanf("%d",&c);
for(;c>0;c--)
{
// 입력 및 그래프 정보 G 셋팅
int v,e,n;
scanf("%d%d%d",&v,&e,&n);
G.resize(v);
int a,b,t;
for(int i=0;i<e;i++)
{
scanf("%d%d%d",&a,&b,&t);
a--; b--;
G[a].push_back(make_pair(t,b));
G[b].push_back(make_pair(t,a));
}

// 다익스트라
for(int i=0;i dist[i]=INF;
dist[0]=0;
Q.push(make_pair(0,0));
while(!Q.empty())
{
int cur=Q.top().first,index=Q.top().second;
Q.pop();
if(cur<=dist[index])
{
for(int i=0;i {
if(dist[G[index][i].second]>cur+G[index][i].first)
{
dist[G[index][i].second]=cur+G[index][i].first;
Q.push(make_pair(dist[G[index][i].second],G[index][i].second));
}
}
}
}

//dfs1과 dfs2를 돌려 위에서 언급한 최단거리 경로 갯수를 구함
int d1[MAX]={0,},d2[MAX]={0,};
for(int i=0;i<v;i++)
d1[i]=d2[i]=-1;
d1[v-1]=1;
dfs1(0,d1);
d2[0]=1;
dfs2(v-1,d2);
for(int i=0;i<v;i++)
{
if(d1[i]==-1)
d1[i]=0;
if(d2[i]==-1)
d2[i]=0;
}

// 확률을 알고자 하는 노드 번호를 입력받아 기약분수 계산하여 출력
for(int i=0;i<n;i++)
{
int tmp,num,denum;
scanf("%d",&tmp);
num=d1[tmp-1]*d2[tmp-1];
denum=d1[0];
tmp=gcd(num,denum);
printf("%d/%d\n",num/tmp,denum/tmp);
}

//그래프 초기화
G.clear();
}
return 0;
}
~~~