[백준]The Other Way(14554)

문제 링크 : [백준]The Other Way(14554)

14554번: The Other Way

 

문제 설명

N개의 노드와 M개의 양방향 간선이 주어질 때, 시작점에서 도착점까지 최단거리로 가는 경로의 갯수를 구하세요.

입력

N(노드의 갯수, 1 <= N <= 100,000)

M(간선의 갯수, 1 <= M <= 300,000)

S E(시작점, 도착점)

F_i T_i C_i(간선의 정보) 

3 4 1 3
1 2 1
2 1 1
2 3 1
1 3 2

 

출력

3

 

카테고리

#다익스트라

 

시간 복잡도 상한

O(MlogM)

 

해결 방법

1. 다익스트라를 이용하면 출발점과 도착점 사이의 최단거리를 구할 수 있습니다.
2. 이 때 큐에넣는 정보에 출발점, 도착점, 비용을 저장합니다.
3. 큐에서 간선 정보가 뽑힐 때, 도착점에 출발지에서 출발한 경우의 수를 저장합니다.
   1. 시작점에서 출발하는 경우의 수는 1이 되며,
   2. 예제의 경우, 1에서 2로 가는 경우가 2가지가 됩니다.
   3. 3으로 오는 경우는, 2를 통해서 오는 2가지 + 1에서 직접 오는 1가지, 총 3가지가 됩니다.
4. 만약 특정 노드에 도착하는 비용이 같다면, 그 때 출발지에서 오는 경우의 수를 누적하여 더해줍니다.

시간복잡도

O(N+MlogM)

코드

#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
#define N 100001
using namespace std;
typedef long long L;
typedef pair<int,int>P;
int n,m,s,e,f[N]={1},x,y,z;
L d[N];
vector<P>v[N];
struct A{
    A(int f,int t,L c):f(f),t(t),c(c){}
    int f,t;
    L c;
    bool operator<(const A&a)const{return c>a.c;}
};
priority_queue<A>q;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>s>>e;
    for(x=1;x<=n;x++)d[x]=9999999999999999;
    while(m--){
        cin>>x>>y>>z;
        v[x].push_back({y,z});
        v[y].push_back({x,z});
    }
    q.push(A(0,s,0));
    while(!q.empty()){
        A c=q.top();q.pop();
        if(d[c.t]<c.c)continue;
        f[c.t]=(f[c.t]+f[c.f])%1000000009;
        if(d[c.t]==c.c)continue;
        d[c.t]=c.c;
        for(P x:v[c.t])if(!f[x.first])q.push(A(c.t,x.first,c.c+x.second));
    }
    cout<<f[e];
}