22019 - パレード (Parade)

작성일 | In

  • 문제 설명

    정점 $N(1\leq N \leq 1000)$개, 가중치가 있는 단방향 간선 $M(1 \leq M \leq 1000)$개 로 이루어진 그래프에서 정점 $1$에서 $N$까지 최단 경로가 $L(1 \leq L \leq 10^9)$​ 이하가 되도록 간선 방향을 뒤집을 때, 뒤집어야 하는 간선의 최소 갯수를 구하는 문제입니다.

  • 해설

    $dis[v][x]$를 정점 $v$까지 $x$​번의 뒤집음으로 도달 가능한 최단거리라고 정의하고 dijkstra알고리즘을 사용하여 최단거리를 구해주면 됩니다. 시간복잡도는 $O(M +N^2\log N^2)$입니다.

  • 코드

    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
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    #include "bits/stdc++.h"
#ifndef ONLINE_JUDGE
#include "headers/debug.h"
#else
#define debug(...) 42
#endif
  
using namespace std;
  
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
#define LLINF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
#define uniq(x) sort(all(x)); x.resize(unique(all(x))-x.begin());
#define sz(x) (int)x.size()
#define pw(x) (1LL<<x)
#define pb push_back
  
using pii = pair<int, int>;
using ll = long long;
using ld = long double;
const ll MOD = 1e9 + 7;
const long double PI = acos(-1.0);
  
struct cmp {
    bool operator() (pair<int, pii> a, pair<int, pii> b) {
        return a.ff > b.ff;
    }
};
  
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m, l; cin >> n >> m >> l;
    vector<vector<pii>> g(n), rg(n);
    for(int i=0; i<m; i++) {
        int u, v, x; cin >> u >> v >> x;
        u--, v--;
        g[u].push_back({v, x});
        rg[v].push_back({u, x});
    }   
    vector<vector<int>> dis(n, vector<int>(m+1, INF));
    dis[0][0] = 0;
    priority_queue<pair<int, pii>, vector<pair<int, pii>>, cmp> pq;
    pq.push({0, {0, 0}});
    while(sz(pq)) {
        int curdis = pq.top().ff;
        int curid = pq.top().ss.ff;
        int cursw = pq.top().ss.ss; pq.pop();
        if(dis[curid][cursw] ^ curdis) continue;
        for(auto [nxtid, nxtdis] : g[curid]) {
            if(dis[nxtid][cursw] > curdis + nxtdis) {
                dis[nxtid][cursw] = curdis + nxtdis;
                pq.push({dis[nxtid][cursw], {nxtid, cursw}});
            }
        }
        for(auto [nxtid, nxtdis] : rg[curid]) {
            if(cursw+1<=m && dis[nxtid][cursw+1] > curdis + nxtdis) {
                dis[nxtid][cursw+1] = curdis + nxtdis;
                pq.push({dis[nxtid][cursw+1], {nxtid, cursw + 1}});
            }
        }
    }
    for(int i=0; i<=m; i++) {
        if(dis[n-1][i] <= l) {
            cout << i << '\n';
            return 0;
        }
    }
    cout << -1 << '\n';
}