Submission #853690

#	Time	Username	Problem	Language	Result	Execution time	Memory
853690		lftroq	Commuter Pass (JOI18_commuter_pass)	C++14	24 / 100	335 ms	49660 KiB

commuter_pass

/*
                     ,
                ,.  | \
               |: \ ; :\
               :' ;\| ::\
                \ : | `::\
                _)  |   `:`.
              ,' , `.    ;: ;
            ,' ;:  ;"'  ,:: |_
           /,   ` .    ;::: |:`-.__
        _,' _o\  ,::.`:' ;  ;   . '
    _,-'           `:.          ;""\,
 ,-'                     ,:         `-;,
 \,                       ;:           ;--._
  `.______,-,----._     ,' ;:        ,/ ,  ,`
         / /,-';'  \     ; `:      ,'/,::.:::
       ,',;-'-'_,--;    ;   :.   ,',',;::::::
      ( /___,-'     `.     ;::,,'o/  ,:::::::
       `'             )    ;:,'o /  ;"-   -::
                      \__ _,'o ,'         ,::
                         ) `--'       ,..::::
      _lftroq_           ; `.        ,:::::::
                          ;  ``::.    :::::::
*/
#include <bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MOD 1000000007LL
#define MOD2 998244353LL
#define endl '\n'
#define INFINITE 2147483647LL
#define INFINITE2 9223372036854775807
#define llll pair<ll,ll>
#define ldld pair<ld,ld>
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using namespace std;

vector<llll> graph[400005];
ll u[200005],v[200005],w[200005],d[100005],d1[100005];

void dijkstra(ll s)
{
    memset(d,0x3f,sizeof(d));
    priority_queue<llll,vector<llll>,greater<llll>> pq;
    d[s]=0;
    pq.push({d[s],s});
    while(pq.size())
    {
        ll u=pq.top().se;
        pq.pop();
        for(int i=0;i<graph[u].size();i++)
        {
            ll v=graph[u][i].fi,w=graph[u][i].se;
            if(d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                pq.push({d[v],v});
            }
        }
    }
}

void dijkstra1(ll s)
{
    memset(d1,0x3f,sizeof(d1));
    priority_queue<llll,vector<llll>,greater<llll>> pq;
    d1[s]=0;
    pq.push({d1[s],s});
    while(pq.size())
    {
        ll u=pq.top().se;
        pq.pop();
        for(int i=0;i<graph[u].size();i++)
        {
            ll v=graph[u][i].fi,w=graph[u][i].se;
            if(d1[v]>d1[u]+w)
            {
                d1[v]=d1[u]+w;
                pq.push({d1[v],v});
            }
        }
    }
}

void solve()
{
    ll n,m,s,t,x,y;
    cin >> n >> m >> s >> t >> x >> y;
    s--;t--;x--;y--;
    for(int i=1;i<=m;i++)
    {
        cin >> u[i] >> v[i] >> w[i];
        u[i]--;v[i]--;
        graph[u[i]].push_back({v[i],w[i]});
        graph[v[i]].push_back({u[i],w[i]});
        graph[3*n+u[i]].push_back({3*n+v[i],w[i]});
        graph[3*n+v[i]].push_back({3*n+u[i],w[i]});
    }
    dijkstra(s);
    dijkstra1(t);
    for(int i=1;i<=m;i++)
    {
        if(d[u[i]]+w[i]+d1[v[i]]==d[t])
        {
            graph[n+u[i]].push_back({n+v[i],0});
            graph[2*n+v[i]].push_back({2*n+u[i],0});
        }
        else if(d[v[i]]+w[i]+d1[u[i]]==d[t])
        {
            graph[2*n+u[i]].push_back({2*n+v[i],0});
            graph[n+v[i]].push_back({n+u[i],0});
        }
    }
    for(int i=0;i<n;i++)
    {
        graph[i].push_back({n+i,0});
        graph[i].push_back({2*n+i,0});
        graph[n+i].push_back({3*n+i,0});
        graph[2*n+i].push_back({3*n+i,0});
    }
//    for(int i=0;i<4*n;i++)
//    {
//        cout << i << ": ";
//        for(int j=0;j<graph[i].size();j++) cout << graph[i][j].fi << " " << graph[i][j].se << "    ";
//        cout << endl;
//    }
    dijkstra(x);
    cout << min({d[y],d[n+y],d[2*n+y],d[3*n+y]}) << endl;
}

int main()
{
    fastIO
    //freopen("hanhhhh.inp","r",stdin);
    //freopen("hanhhhh.out","w",stdout);
    ll t=1;
    //cin >> t;
    while(t--)
    solve();
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(ll)':
commuter_pass.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for(int i=0;i<graph[u].size();i++)
      |                     ~^~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dijkstra1(ll)':
commuter_pass.cpp:77:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for(int i=0;i<graph[u].size();i++)
      |                     ~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 24 / 24
• Subtask 4: 0 / 45