Submission #380979

#	Time	Username	Problem	Language	Result	Execution time	Memory
380979		PedroBigMan	Relay Marathon (NOI20_relaymarathon)	C++14	100 / 100	2625 ms	370884 KiB

RelayMarathon

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=a; i<b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 100000000000000000LL
ll insig;
#define In(vecBRO, LENBRO) REP(IBRO,0,LENBRO) {cin>>insig; vecBRO.pb(insig);}
void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}

class WG //everything works for weighted directed graphs
{
    public:
    ll N; vector<vector<pl> > adj;
    vector<bool> pr; vector<ll> nv;
    
    WG(vector<vector<pl> > ad)
    {
        adj=ad; N=adj.size();
        REP(i,0,N) {pr.pb(false); nv.pb(0);}
    }
    
    void Reset()
    {
        REP(i,0,N) {pr[i]=false;nv.pb(0);}
    }
    
    vector<ll> Djikstra(ll s)
    {
        Reset();
        vector<ll> d; REP(i,0,N) {d.pb(INF);}
        d[s]=0;
        priority_queue<pl> q;
        q.push(mp(0,s));
        ll cur;
        while(!q.empty())
        {
            cur=q.top().ss; q.pop();
            if(pr[cur]) {continue;}
            pr[cur]=true; 
            REP(i,0,adj[cur].size())
            {
                if(d[adj[cur][i].ff]>d[cur]+adj[cur][i].ss)
                {
                    d[adj[cur][i].ff]=d[cur]+adj[cur][i].ss;
                    q.push(mp(-d[adj[cur][i].ff],adj[cur][i].ff));
                }
            }
        }
        return d;
    }
    
    vector<pl> Djikstra_MS(vector<ll> sn) //Djikstra Multi-sourced, ans[i].ff=d(i,sn), ans[i].ss=member of sn closest to i
    {
        Reset();
        ll K=sn.size();
        vector<pl> d; REP(i,0,N) {d.pb(mp(INF,-1LL));}
        REP(i,0,K) {d[sn[i]]=mp(0LL,sn[i]);}
        priority_queue<pl> q;
        REP(i,0,K) {q.push(mp(0,sn[i]));}
        ll cur;
        while(!q.empty())
        {
            cur=q.top().ss; q.pop();
            if(pr[cur]) {continue;}
            pr[cur]=true; 
            REP(i,0,adj[cur].size())
            {
                if(d[adj[cur][i].ff].ff>d[cur].ff+adj[cur][i].ss)
                {
                    d[adj[cur][i].ff].ff=d[cur].ff+adj[cur][i].ss;
                    d[adj[cur][i].ff].ss=d[cur].ss;
                    q.push(mp(-d[adj[cur][i].ff].ff,adj[cur][i].ff));
                }
            }
        }
        return d;
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll N,M,K; cin>>N>>M>>K; vector<ll> A; vector<pl> xx; vector<vector<pl> > adj; REP(i,0,N) {adj.pb(xx);}
    pl cur; ll we;
    REP(i,0,M) {cin>>cur.ff>>cur.ss>>we; cur.ff--; cur.ss--; adj[cur.ff].pb(mp(cur.ss,we)); adj[cur.ss].pb(mp(cur.ff,we));}
    WG G(adj);
    In(A,K); REP(i,0,K) {A[i]--;}
    ll ans=INF; pl co; ll sp=INF;
    vector<pl> d=G.Djikstra_MS(A);
    REP(i,0,N)
    {
        REP(j,0,adj[i].size())
        {
            if(d[i].ss==d[adj[i][j].ff].ss) {continue;}
            if(d[i].ff+d[adj[i][j].ff].ff+adj[i][j].ss<sp)
            {
                sp=d[i].ff+d[adj[i][j].ff].ff+adj[i][j].ss;
                co=mp(d[i].ss,d[adj[i][j].ff].ss);
            }
        }
    }
    ans=sp;
    sp=INF;
    pl co2;
    A.erase(find(whole(A),co.ff));
    A.erase(find(whole(A),co.ss));
    d=G.Djikstra_MS(A);
    REP(i,0,N)
    {
        REP(j,0,adj[i].size())
        {
            if(i==co.ff || i==co.ss || adj[i][j].ff==co.ff || adj[i][j].ff==co.ss) {continue;}
            if(d[i].ss==d[adj[i][j].ff].ss) {continue;}
            if(d[i].ff+d[adj[i][j].ff].ff+adj[i][j].ss<sp)
            {
                sp=d[i].ff+d[adj[i][j].ff].ff+adj[i][j].ss;
                co2=mp(d[i].ss,d[adj[i][j].ff].ss);
            }
        }
    }
    ans+=sp;
    
    vector<ll> d1=G.Djikstra(co.ff); 
    vector<ll> d2=G.Djikstra(co.ss);
    
    ll mindist1=INF; ll par1;  ll mindist2=INF; ll par2;
    REP(j,0,K) 
    {
        ll i=A[j];
        if(i==co.ff || i==co.ss) {continue;}
        if(d1[i]<mindist1) {mindist1=d1[i]; par1=i;}
    }
    REP(j,0,K) 
    {
        ll i=A[j];
        if(i==co.ff || i==co.ss || i==par1) {continue;}
        if(d2[i]<mindist2) {mindist2=d2[i]; par2=i;}
    }
    ans=min(ans,mindist1+mindist2);
    
    mindist1=INF; mindist2=INF;
    REP(j,0,K) 
    {
        ll i=A[j];
        if(i==co.ff || i==co.ss) {continue;}
        if(d2[i]<mindist2) {mindist2=d2[i]; par2=i;}
    }
    REP(j,0,K) 
    {
        ll i=A[j];
        if(i==co.ff || i==co.ss || i==par2) {continue;}
        if(d1[i]<mindist1) {mindist1=d1[i]; par1=i;}
    }
    ans=min(ans,mindist1+mindist2);
    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

RelayMarathon.cpp: In function 'void Out(std::vector<long long int>)':
RelayMarathon.cpp:17:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
   28 | void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}
      |                             ~~~~~~~~~~~~
RelayMarathon.cpp:28:25: note: in expansion of macro 'REP'
   28 | void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}
      |                         ^~~
RelayMarathon.cpp: In member function 'std::vector<long long int> WG::Djikstra(ll)':
RelayMarathon.cpp:17:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
   60 |             REP(i,0,adj[cur].size())
      |                 ~~~~~~~~~~~~~~~~~~~
RelayMarathon.cpp:60:13: note: in expansion of macro 'REP'
   60 |             REP(i,0,adj[cur].size())
      |             ^~~
RelayMarathon.cpp: In member function 'std::vector<std::pair<long long int, long long int> > WG::Djikstra_MS(std::vector<long long int>)':
RelayMarathon.cpp:17:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
   86 |             REP(i,0,adj[cur].size())
      |                 ~~~~~~~~~~~~~~~~~~~
RelayMarathon.cpp:86:13: note: in expansion of macro 'REP'
   86 |             REP(i,0,adj[cur].size())
      |             ^~~
RelayMarathon.cpp: In function 'int main()':
RelayMarathon.cpp:17:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  113 |         REP(j,0,adj[i].size())
      |             ~~~~~~~~~~~~~~~~~    
RelayMarathon.cpp:113:9: note: in expansion of macro 'REP'
  113 |         REP(j,0,adj[i].size())
      |         ^~~
RelayMarathon.cpp:17:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  131 |         REP(j,0,adj[i].size())
      |             ~~~~~~~~~~~~~~~~~    
RelayMarathon.cpp:131:9: note: in expansion of macro 'REP'
  131 |         REP(j,0,adj[i].size())
      |         ^~~
RelayMarathon.cpp:172:33: warning: 'par2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  172 |         if(i==co.ff || i==co.ss || i==par2) {continue;}
      |            ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
RelayMarathon.cpp:157:33: warning: 'par1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  157 |         if(i==co.ff || i==co.ss || i==par1) {continue;}
      |            ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 12 / 12
• Subtask 3: 25 / 25
• Subtask 4: 58 / 58