일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- lis
- 삼분탐색
- 구현
- DP
- 백준
- 투포인터
- 다익스트라
- 이분매칭
- LazyPropagation
- boj
- 정렬
- 브루트포스
- 좌표압축
- DisjointSet
- 펜윅트리
- dfs
- BFS
- 누적합
- 세그먼트트리
- 이분탐색
- 수학
- 비트마스크
- 플로이드와샬
- 그리디
- 크루스칼
- MST
- 이진탐색
- 에라토스테네스의 체
- lca
- 위상정렬
Archives
- Today
- Total
lastknight00
[백준]The Other Way(14554) 본문
문제 링크 : [백준]The Other Way(14554)
문제 설명
N개의 노드와 M개의 양방향 간선이 주어질 때, 시작점에서 도착점까지 최단거리로 가는 경로의 갯수를 구하세요.
입력
N(노드의 갯수, 1 <= N <= 100,000)
M(간선의 갯수, 1 <= M <= 300,000)
S E(시작점, 도착점)
Fi Ti Ci(간선의 정보)
3 4 1 3
1 2 1
2 1 1
2 3 1
1 3 2
출력
3
카테고리
#다익스트라
시간 복잡도 상한
O(MlogM)
해결 방법
- 다익스트라를 이용하면 출발점과 도착점 사이의 최단거리를 구할 수 있습니다.
- 이 때 큐에넣는 정보에 출발점, 도착점, 비용을 저장합니다.
- 큐에서 간선 정보가 뽑힐 때, 도착점에 출발지에서 출발한 경우의 수를 저장합니다.
- 시작점에서 출발하는 경우의 수는 1이 되며,
- 예제의 경우, 1에서 2로 가는 경우가 2가지가 됩니다.
- 3으로 오는 경우는, 2를 통해서 오는 2가지 + 1에서 직접 오는 1가지, 총 3가지가 됩니다.
- 만약 특정 노드에 도착하는 비용이 같다면, 그 때 출발지에서 오는 경우의 수를 누적하여 더해줍니다.
시간복잡도
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];
}
'PS' 카테고리의 다른 글
[백준]오등큰수(17299) (0) | 2020.10.30 |
---|---|
[백준]특정한 최단 경로(1504) (0) | 2020.10.29 |
[백준]물대기(1368) (0) | 2020.10.24 |
[백준]평균값 수열(5485) (3) | 2020.10.02 |
[백준]무한이진트리(2078) (0) | 2020.10.02 |
Comments