Submission #666863

#	Time	Username	Problem	Language	Result	Execution time	Memory
666863		kirakaminski968	Robot (JOI21_ho_t4)	C++17	100 / 100	783 ms	113116 KiB

Main

#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define setp() cout << setprecision(15)
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;
struct Edge{
  int nxt,c; 
  ll e; 
};
int n,m; 
ll dist[N][2] ;
vector<Edge> g[N]; 
map<int,ll> s[N]; 
int t; 
void solve(){
  cin >> n >> m; 
  for(int i = 0;i<m;++i){
    int u,v,c;
    ll e; 
    cin >> u >> v >> c >> e; 
    g[u].push_back({v,c,e}); 
    g[v].push_back({u,c,e}); 
    s[u][c] += e; 
    s[v][c] += e; 
  }
  for(int i = 1;i<=n;++i) dist[i][0] = dist[i][1] = 1e18; 
  priority_queue<array<ll,3>> pq; 
  vector<bool> vis[2]; 
  vis[0].resize(n+1); 
  vis[1].resize(n+1); 
  dist[n][0] = 0; 
  pq.push({0,n,-1}); 
  while(pq.size()){
    int v = pq.top()[1], cc = pq.top()[2]; 
    ll D = -pq.top()[0]; 
    pq.pop(); 
    if(vis[cc == -1][v]) continue; 
    vis[cc == -1][v] = 1; 
    for(auto E : g[v]){
      int c = E.c, nxt = E.nxt; 
      ll e = E.e, val = s[nxt][c]; 
      if(cc == c) e = 0; 
      if(D + e < dist[nxt][0]){
        dist[nxt][0] = D+e; 
        pq.push({-dist[nxt][0],nxt,-1}); 
      }
      if(D - e + val < dist[nxt][1]){
        dist[nxt][1] = D-e+val; 
        pq.push({-dist[nxt][1],nxt,c}); 
      }
    }
  }
  if(min(dist[1][0],dist[1][1]) == 1e18) cout << -1; 
  else cout << min(dist[1][0],dist[1][1]); 
}
int main(){
  solve(); 
  return 0; 
}

• Subtask 1: 34 / 34
• Subtask 2: 24 / 24
• Subtask 3: 42 / 42