# Untitled

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;