oj.uz

Submission #910844

# Submission time Handle Problem Language Result Execution time Memory
910844 2024-01-18T08:27:50 Z vjudge1 Autobus (COCI22_autobus) C++17
0 / 70
 2 ms 568 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define pb push_back

#define TASKNAME "NAME"

void init()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ///freopen(TASKNAME".INP","r",stdin); freopen(TASKNAME".OUT","w",stdout);
}

const int SZ = 75;
const ll INF = INT_MAX / 2, MOD = 1e9+7, INFLL = 2e18;
const double epsilon = 1e-3;

int n,m,k,q;

struct Edge
{
    int v;
    ll w;
    Edge(int _v = 0, ll _w = 0) : v(_v), w(_w) {}
};

vector<Edge> adj[SZ];
ll d[SZ][SZ];
bool vis[SZ][SZ];

void dijkstra(int s)
{
    for(int i = 1; i <= n; i++)
    {
        d[s][i] = INFLL;
    }
    d[s][s] = 0;
    for(int i = 1; i <= min(k,n); i++)
    {
        int best;
        ll mx = INFLL;
        for(int u = 1; u <= n; u++)
        {
            if(d[s][u] < mx && !vis[s][u])
            {
                best = u;
                mx = d[s][u];
            }
        }
        vis[s][best] = true;
        for(Edge e : adj[best])
        {
            int v = e.v;
            ll w = e.w;
            if(d[s][v] > d[s][best] + w)
            {
                d[s][v] = d[s][best] + w;
            }
        }
    }
}

int main()
{
    init();
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int u,v;
        ll w;
        cin >> u >> v >> w;
        adj[u].pb({v,w});
    }
    cin >> k >> q;
    for(int u = 1; u <= n; u++)
    {
        dijkstra(u);
    }
    while(q--)
    {
        int u,v;
        cin >> u >> v;
        cout << (d[u][v] == INFLL ? -1 : d[u][v]) << '\n';
    }
}

Compilation message

Main.cpp: In function 'void dijkstra(int)':
Main.cpp:48:13: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |         int best;
      |             ^~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 568 KB Output is correct
2 Incorrect 2 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -