# Flight_Discount_CSES

unknown
c_cpp
2 years ago
3.5 kB
1
Indexable
Never
```//PPAP_1264589
#include "bits/stdc++.h"
#define up(i,a,b) for (int i = a; i <= b; i++)
#define pii pair<int, long long>
#define plli pair<long long, int>
#define f first
#define s second
#define ep emplace_back
using namespace std;

const int maxn = 1e5 + 10;
int n,m;
vector<pii> a[maxn];
vector<pii> b[maxn];
struct edge{
int u,v;
long long w;
};
vector<edge> E;

void in(){
cin >> n >> m;
int u,v;
long long w;
up(i,1,m){
cin >> u >> v >> w;
a[u].ep(v, w);
b[v].ep(u, w);
E.push_back({u, v, w});
}
}

namespace Solution1{
priority_queue<plli, vector<plli>, greater<plli>> P;
long long d1[maxn], dn[maxn];

void minimalize(const long long curw, pii x, long long d[]){
int v = x.f;
long long w = x.s;
if (d[v] > curw + w){
d[v] = curw + w;
P.push({d[v], v});
}
}

void Dijkstra(int root, long long d[]){
fill(d+1, d+n+1, 1e18 + 31);
d[root] = 0;
P.push({0, root});
while (!P.empty()){
int u = P.top().s;
long long curw = P.top().f;
P.pop();
if (curw > d[u]) continue;
if (root == 1) for (pii x : a[u]){
minimalize(curw, x, d);
}
if (root == n) for (pii x : b[u]){
minimalize(curw, x, d);
}
}
}

long long check_edges(){
long long res = 1e18 + 31;
for (auto e : E){
int u = e.u;
int v = e.v;
long long w = e.w;
long long newval = d1[u] + dn[v] + w/2;
if (res > newval) res = newval;
}
return res;
}

void MAIN(){
in();
Dijkstra(1, d1);
Dijkstra(n, dn);
cout << check_edges();
}
}

namespace Solution2{
struct NODE{
long long val;
int nod;
bool used;
};
inline bool operator < (const NODE& x, const NODE& y){
return x.val > y.val;
}   priority_queue<NODE> P;

long long d[2][maxn];

void minimalize(long long curw, pii x, bool curused){
int v = x.f;
long long w = x.s;
long long newval;

newval = curw + w;
if (d[curused][v] > newval){
d[curused][v] = newval;
P.push({newval, v, curused});
}

if (!curused){
newval = curw + w/2;
if (d[1][v] > newval){
d[1][v] = newval;
P.push({newval, v, 1});
}
}
}

void Dijkstra(){
fill(d[0]+1, d[0]+n+1, 1e18 + 31);
fill(d[1]+1, d[1]+n+1, 1e18 + 31);
d[0][1] = 0;
d[1][1] = 0;
P.push({0, 1, 0});
while (!P.empty()){
int u = P.top().nod;
long long curw = P.top().val;
bool curused = P.top().used;
P.pop();
if (curw > d[curused][u]) continue;
for (pii x : a[u]){
minimalize(curw, x, curused);
}
}
}

void MAIN(){
in();
Dijkstra();
cout << d[1][n];
}
}

signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);

//Solution1::MAIN();
Solution2::MAIN();
}

// Algorithmic logic```