wa
unknown
c_cpp
2 years ago
2.6 kB
4
Indexable
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double lld; #define pll pair<ll,ll> #define vll vector<ll> #define ln "\n" #define pii pair<int,int> #define fi first #define se second #define pb push_back #define mp make_pair #define be begin #define ub upper_bound #define lb lower_bound #define bi binary_search #define sll set <ll> #define msll multiset <ll> #define vpll vector <pair<ll,ll>> #define mll map <ll,ll> #define all(v) v.begin(),v.end() #define mem1(a) memset(a,-1,sizeof(a)) #define mem0(a) memset(a,0,sizeof(a)) #define i1(x) cin>>x #define i2(x1,x2) cin>>x1>>x2 #define i3(x1,x2,x3) cin>>x1>>x2>>x3 #define i4(x1,x2,x3,x4) cin>>x1>>x2>>x3>>x4 #define o1(x) cout<<x<<ln #define o2(x1,x2) cout<<x1<<" "<<x2<<ln #define o3(x1,x2,x3) cout<<x1<<" "<<x2<<" "<<x3<<ln #define o4(x1,x2,x3,x4) cout<<x1<<" "<<x2<<" "<<x3<<" "<<x4<<ln #define rep(i,s,e) for(ll i=s;i<e;i++) #define rrep(i,s,e) for(ll i=s-1;i>=e;i--) #define geta(a,n) for(ll i=0;i<n;i++)cin>>a[i]; const ll mod = 1e9 + 7; vector <pll> adj[200100]; vector <vll> dis(200100, vll(2, 1e18)); vll vis(200100, 0); void solve() { ll n, m; i2(n, m); rep(i, 0, m) { ll k1, k2, k3; i3(k1, k2, k3); adj[k1].push_back({k2, k3}); } priority_queue <pair <ll, pll>> pq; dis[1][0] = 0; pq.push({0, {1, 0}}); while (!pq.empty()) { pair <ll, pll> p = pq.top(); pq.pop(); ll y = p.first; ll x = p.second.first; // if (vis[x]==1) // continue; // vis[x]++; //o3(p.first, p.second.first, p.second.second); //o2(x,y); for (auto i : adj[x]) { //o3(dis[i.first],dis[x],i.second); if (p.second.second == 0) { if (dis[i.first][0] > dis[x][0] + i.second) { dis[i.first][0] = dis[x][0] + i.second; //o2(i.first,dis[i.first]); pq.push({ -dis[i.first][0], {i.first, p.second.second}}); } } else { if (dis[i.first][1] > dis[x][1] + i.second) { dis[i.first][1] = dis[x][1] + i.second; //o2(i.first,dis[i.first]); pq.push({ -dis[i.first][1], {i.first, p.second.second}}); } } if (p.second.second == 0) { if (dis[i.first][1] > dis[x][0] + i.second / 2) { dis[i.first][1] = dis[x][0] + i.second / 2; //o2(i.first,dis[i.first]); pq.push({ -dis[i.first][1], {i.first, 1}}); } } } } o1(dis[n][1]); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ll t = 1; //cin >> t; srand(time(0)); for (ll i = 1; i <= t; i++) { //cout << "Case #" << i << ": "; solve(); } return 0; }
Editor is loading...