Submission #1084344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084344		Equinox	Ceste (COCI17_ceste)	C++17	0 / 160	2576 ms	131072 KiB

ceste

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef complex<double> cpx;
#define fastio cin.tie(0)->sync_with_stdio(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define compress(x) x.erase(unique(all(x)),x.end())
#define ff first
#define ss second

struct Edge{
    ll x,t,c;
};

ll n,m,dist[2010];
pll dsum[2010];
vector<Edge> g[2010];
map<pll,pll> mp;
ll ans[2010];

pll dijkstra(ll x, ll a, ll b){
    for(int i=1;i<=n;i++){
        dist[i] = (ll)1e15;
        dsum[i] = {(ll)1e15,(ll)1e15};
    }
    dist[1] = 0;
    dsum[1] = {0,0};
    priority_queue<pair<pll,pll> > pq;
    pq.push({{0,1},{0,0}});
    while(!pq.empty()){
        ll c = pq.top().ff.ss, w = -pq.top().ff.ff;
        ll ca = pq.top().ss.ff, cb = pq.top().ss.ss;
        pq.pop();
        if(dist[c]<w) continue;
        for(auto i:g[c]){
            ll nx = i.x, nw = w + a*i.t + b*i.c;
            ll na = ca + i.t, nb = cb + i.c;
            if(nw<dist[nx]){
                dist[nx] = nw;
                dsum[nx] = {na,nb};
                //cout << i.x << " " << c << " " << nx << "\n";
                pq.push({{-dist[nx],nx},{na,nb}});
            }
        }
    }
    for(int i=2;i<=n;i++){
        ans[i] = min(ans[i],dsum[i].ff*dsum[i].ss);
        mp[{a,b}] = dsum[i];
    }
    if(dist[x]>(ll)1e14) return dsum[x];
    else{
        return dsum[x];
    }
}

void qhull(ll x, pll a, pll b){
    ll ta = a.ss-b.ss, tb = b.ff-a.ff;
    pll c = mp[{ta,tb}];
    if(c.ff==0&&c.ss==0) c = dijkstra(x,a.ss-b.ss,b.ff-a.ff);
    if((b.ff-a.ff)*(c.ss-a.ss)==(b.ss-a.ss)*(c.ff-a.ff)) return;
    qhull(x,a,c); qhull(x,c,b);
}

ll solve(ll x){
    pll lc = dijkstra(x,1,0);
    pll rc = dijkstra(x,0,1);
    // cout << lc.ff << " " << lc.ss << "\n";
    // cout << rc.ff << " " << rc.ss << "\n";
    if(lc.ff>(ll)1e14) return -1;
    qhull(x,lc,rc);
    return ans[x];
}

int main(){
    fastio;
    cin >> n >> m;
    for(int i=0;i<m;i++){
        ll x,y,z,w; cin >> x >> y >> z >> w;
        g[x].push_back({y,z,w});
        g[y].push_back({x,z,w});
    }
    for(int i=2;i<=n;i++){
        ans[i] = (ll)1e18;
    }
    for(int i=2;i<=n;i++){
        cout << solve(i) << "\n";
    }
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 16
• Subtask 3: 0 / 16
• Subtask 4: 0 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 16
• Subtask 7: 0 / 16
• Subtask 8: 0 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16