Submission #718094

#TimeUsernameProblemLanguageResultExecution timeMemory
718094KalashnikovRobot (JOI21_ho_t4)C++17
0 / 100
718 ms58320 KiB
#include <bits/stdc++.h> #define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout) #define all(a) a.begin() , a.end() #define F first #define S second using namespace std; using ll = long long; #define int ll const int N = 1e5+5 , inf = 2e9 + 7; const ll INF = 1e18 , mod = 1e9+7 , P = 6547; map<int,vector<int>> mp[N]; vector<pair<int,int>> g[N]; void solve(int tc) { int n, m; cin >> n >> m; vector<array<int,4>> vec; for(int i = 1; i <= m; i ++) { int a, b,c, p; cin >> a >> b >> c >> p; vec.push_back({a,b,c,p}); mp[a][c].push_back(b); mp[b][c].push_back(a); } for(auto [a,b,c,p]: vec) { if(mp[a][c].size() == 1) { g[a].push_back({b,0}); } else { g[a].push_back({b,p}); } if(mp[b][c].size() == 1) { g[b].push_back({a,0}); } else { g[b].push_back({a,p}); } if(mp[a][c].size() == 2) { g[mp[a][c][0]].push_back({mp[a][c][1], p}); g[mp[a][c][1]].push_back({mp[a][c][0], p}); } } vector<ll> d(n+1, INF); d[1] = 0; set<pair<int,int>> st; st.insert({0, 1}); while(st.size()) { pair<int,int> cur = *st.begin(); st.erase(cur); for(auto to: g[cur.S]) { if(cur.F + to.S < d[to.F]) { st.erase({d[to.F], to.F}); d[to.F] = cur.F + to.S; st.insert({d[to.F], to.F}); } } } if(d[n] == INF) d[n] = -1; cout << d[n]; } /* */ main() { ios; int tt = 1 , tc = 0; // cin >> tt; while(tt --) { solve(++tc); } return 0; }

Compilation message (stderr)

Main.cpp:69:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   69 | main() {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...