oj.uz

Submission #783739

# Submission time Handle Problem Language Result Execution time Memory
783739 2023-07-15T09:28:47 Z Cookie Ferries (NOI13_ferries) C++14
40 / 40
 307 ms 31832 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("FEEDING.INP");
ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
using u128 = __uint128_t;
const int x[4] = {1, -1, 0, 0};
const int y[4] = {0, 0, 1, -1};
const ll mod = 1e9 + 7, inf = 1e16;
const int mxn = 1e5 + 5;

int n, m;
vt<int>adj[mxn + 1];
multiset<int>ms[mxn + 1];
ll dis[mxn + 1];
bool vis[mxn + 1];
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    forr(i, 0, m){
        int a, b, c; cin >> a >> b >> c;
        adj[b].pb(a); ms[a].insert(c);
    }
    for(int i = 1; i <= n; i++)dis[i] = inf;
    priority_queue<pll, vt<pll>,greater<pll>>pq; dis[n] = 0;
    pq.push({dis[n], n});
    while(!pq.empty()){
        auto [dd, u] = pq.top(); pq.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(auto v: adj[u]){
            int cost = *ms[v].rbegin();
            if(dis[v] > dis[u] + cost){
                dis[v] = dis[u] + cost;
                pq.push({dis[v], v});
            }
            ms[v].erase(ms[v].find(cost));
        }
        
    }
    cout << dis[1];
    return(0);
}

Compilation message

ferries.cpp: In function 'int main()':
ferries.cpp:42:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |         auto [dd, u] = pq.top(); pq.pop();
      |              ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 5 ms 7520 KB Output is correct
3 Correct 11 ms 9308 KB Output is correct
4 Correct 112 ms 26236 KB Output is correct
5 Correct 115 ms 26176 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7508 KB Output is correct
3 Correct 10 ms 9308 KB Output is correct
4 Correct 51 ms 16276 KB Output is correct
5 Correct 69 ms 18920 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 9556 KB Output is correct
2 Correct 14 ms 9556 KB Output is correct
3 Correct 214 ms 30656 KB Output is correct
4 Correct 200 ms 30936 KB Output is correct
5 Correct 201 ms 30156 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 30568 KB Output is correct
2 Correct 226 ms 30596 KB Output is correct
3 Correct 303 ms 31832 KB Output is correct
4 Correct 243 ms 31816 KB Output is correct
5 Correct 307 ms 31812 KB Output is correct