# 【CSES】1202. Investigation

## [題目連結](https://cses.fi/problemset/task/1202/)

## **時間複雜度**

* $O(ElogV)$

## **解題想法**

這題我第一次看起來覺得很複雜，但是仔細想一下之後就會發現其實沒有很難解，只是將 Dijkstra 搭配上 DP 就可以處理掉了

然後在進行 Dijkstra 的時候要同時追蹤下面四個東西

1. 最短距離：`dis[]`
2. 最短距離的解數量： `routes[]`
3. 最短距離且最少的班機數： `minf[]`
4. 最短距離且最少的班機數： `maxf[]`

對於每個節點 $v$，我們都會考慮他的所有權重為 $w$ 的鄰居 $u$，當我們可以鬆弛邊 $vu$ （dis[v] > dis[u] + w）時，就將變數的值更改成下面這樣

1. 最短距離：`dis[v]` = `dis[u] + w`
2. 最短距離的解數量： `routes[v]` = `routes[u]`
3. 最短距離且最少的班機數： `minf[v]` = `minf[u] + 1`
4. 最短距離且最少的班機數： `maxf[v]` = `maxf[v] + 1`

但跟平常的 Dijkstra 不一樣的是我們還必須考慮到 dis[v] = dis[u] + w 的情況（因為你不會知道當前是不是最段距離），所以當 dis[v] = dis[u] + w 成立時，我們將值更新成下變這樣

1. 最短距離：`dis[v]` 不更新
2. 最短距離的解數量： `routes[v]` = `( routes[v] + routes[u] ) % Mod` ➨ 這邊記得取模
3. 最短距離且最少的班機數： `minf[v]` = `min( minf[v], minf[u] + 1 )`
4. 最短距離且最少的班機數： `maxf[v]` = `max( maxf[v], maxf[u] + 1 )`

## **完整程式**

/* Question : CSES 1202. Investigation */

#include<bits/stdc++.h>
using namespace std;

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pirq(type) priority_queue<type, vector<type>, greater<type>>
#define mem(x, value) memset(x, value, sizeof(x));
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pdd pair<double, double>
#define pb push_back
#define f first
#define s second
#define int long long

const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAXN = 1e5 + 50;
const int Mod = 1e9 + 7;
int n, m, u, v, w, dis[MAXN];
vector<vector<pii>> graph;

struct Node{
    int maxf = 0, minf = 0, routes = 0;
} dp[MAXN];

void dij( int root ){
    pirq(pii) pq;
    pq.push({0, root});
    dis[root] = 0;
    dp[root].routes = 1;
    while( !pq.empty() ){
        int d = pq.top().f;
        int node = pq.top().s;
        pq.pop();

        if( d > dis[node] ) continue;
        for( auto i : graph[node] ){
            int v = i.f;
            int w = i.s; // Weight
            if( d + w == dis[v] ){
                dp[v].routes = ( dp[v].routes + dp[node].routes ) % Mod;
                dp[v].maxf = max( dp[v].maxf, dp[node].maxf + 1);
                dp[v].minf = min( dp[v].minf, dp[node].minf + 1);
            }else if( d + w < dis[v] ){
                dis[v] = d + w;
                dp[v].routes = dp[node].routes;
                dp[v].maxf = dp[node].maxf + 1; 
                dp[v].minf = dp[node].minf + 1;
                pq.push({dis[v], v});
            }
        }
    }
}

signed main(){
    opt;
    cin >> n >> m;
    graph.resize(n+5);
    for( int i = 0 ; i < m ; i++ ){
        cin >> u >> v >> w;
        graph[u].pb({v, w});
    }

    mem(dis, 0x3F);
    dij(1);

    cout << dis[n] << " " << dp[n].routes << " " << dp[n].minf << " " << dp[n].maxf << "\n";
}