Untitled

mail@pastecode.io avatar
unknown
c_cpp
16 days ago
2.4 kB
3
Indexable
Never
// #define Many_SubTask
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(a) begin(a), end(a)
#define pb push_back
#define pii pair<int, int>
#define F first
#define S second
#define mp make_pair
const int mod = 998244353;
const int inf = 1e18;
const int MAXN = 100005;

int n, m;
vector<pii> Map[MAXN];
int dis[MAXN][2], length[MAXN][2];

struct node {
    int idx, val, len, cp;
    bool operator<(node a) const {
        if(val == a.val) return len > a.len;
        return val < a.val;
    }
};

priority_queue<node> pq;

void Dijkstra(int s, int e) {
    for (int i = 1; i <= n; i++) dis[i][0] = dis[i][1] = 1e9;
    dis[s][0] = 0;

    pq.push({s, dis[s][0], length[s][0], 0});

    while (!pq.empty()) {
        auto [src, val, len, cp] = pq.top(); pq.pop();
        if (dis[src][cp] < val) continue;
        else if(dis[src][cp] == val && length[src][cp] > len) continue;

        for (auto [des, val] : Map[src]) {
            // use coupon
            if(!cp){
                if (dis[src][0] + 0 < dis[des][1]) {
                    dis[des][1] = dis[src][0];
                    length[des][1] = length[src][0] + 1;
                    pq.push({des, dis[des][1], length[des][1], 1});
                } else if (dis[src][0] + 0 == dis[des][1] && length[src][0] + 1 > length[des][1]) {
                    length[des][1] = length[src][0] + 1;
                    pq.push({des, dis[des][1], length[des][1], 1});
                }
            }

            // use coupon
            if (dis[src][cp] + val < dis[des][cp]) {
                dis[des][cp] = dis[src][cp] + val;
                length[des][cp] = length[src][cp] + 1;
                pq.push({des, dis[des][cp], length[des][cp], cp});
            } else if (dis[src][cp] + val == dis[des][cp] && length[src][cp] + 1 > length[des][cp]) {
                length[des][cp] = length[src][cp] + 1;
                pq.push({des, dis[des][cp], length[des][cp], cp});
            }
        }
    }
}

// 8 2 3 9
// 6 2 4 9

void solve() {
    cin >> n >> m;
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        Map[u].pb({v, w});
        Map[v].pb({u, w});
    }
    Dijkstra(1, n);
    cout << dis[n][1] << ' ' << length[n][1] - 1 << '\n';
}

signed main() {
    cin.sync_with_stdio(0), cin.tie(0);
    int N = 1;
#ifdef Many_SubTask
    cin >> N;
#endif
    for (int i = 1; i <= N; i++) {
        solve();
    }
}
Leave a Comment