Submission #909608

#	Time	Username	Problem	Language	Result	Execution time	Memory
909608		andrei_iorgulescu	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	787 ms	4060 KiB

ho_t4

#include <bits/stdc++.h>
 
using namespace std;
 
#define int unsigned int
 
const int inf = 1e9;
const int some_fixed_seed = 12345;
 
struct ura
{
    int u,v,c,d;
};
 
int n,m;
vector<ura>e;
int d[205][205];
vector<pair<int,int>>g[205];
 
int getdist(int sursa,int destinatie)
{
    vector<int>dist(n + 1);
    for (int i = 1; i <= n; i++)
        dist[i] = inf;
    priority_queue<pair<int,int>>pq;
    pq.push({0,sursa});
    while (!pq.empty())
    {
        int nod = pq.top().second,cost = -pq.top().first;
        if (nod == destinatie)
            return cost;
        pq.pop();
        if (dist[nod] == inf)
        {
            dist[nod] = cost;
            for (auto vecin : g[nod])
                pq.push({-(cost + vecin.second),vecin.first});
        }
    }
    return inf;
}
 
int tryrev(int idx)
{
    for (int i = 1; i <= n; i++)
        g[i].clear();
    for (int i = 0; i < e.size(); i++)
    {
        if (i == idx)
            g[e[i].v].push_back({e[i].u,e[i].c});
        else
            g[e[i].u].push_back({e[i].v,e[i].c});
    }
    return getdist(1,n) + getdist(n,1);
}
 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i != j)
                d[i][j] = inf;
    for (int i = 1; i <= m; i++)
    {
        ura aux;
        cin >> aux.u >> aux.v >> aux.c >> aux.d;
        e.push_back(aux);
        d[aux.u][aux.v] = min(d[aux.u][aux.v],aux.c);
    }
    //shuffle(e.begin(),e.end(),default_random_engine(some_fixed_seed));
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j],d[i][k] + d[k][j]);
    int ans = d[1][n] + d[n][1];
    for (int i = 0; i < e.size(); i++)
    {
        auto it = e[i];
        int d1 = min(d[1][n],d[1][it.v] + d[it.u][n] + it.c);
        int d2 = min(d[n][1],d[n][it.v] + d[it.u][1] + it.c);
        int cur = d1 + d2 + it.d;
        if (cur < ans)
            ans = min(ans,it.d + tryrev(i));
    }
    if (ans >= inf)
        cout << -1;
    else
        cout << ans;
    return 0;
}
 
/**
hai sa zicem ca dau invert la muchia u->v
costul o sa fie >= cost_rev + min(dist(1,n),cost_edge + dist(1,v) + dist(u,n)) + min(dist(n,1),cost_edge + dist(n,v) + dist(u,1))
dau random shuffle la muchii si verific o muchie doar daca are acest cost < ans
teoretic as verifica log muchii, asa o sa verific ceva mai multe dar hopefully tot putine
**/

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 63 / 63