제출 #853721

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
853721		lftroq	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	431 ms	72816 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[100005],graph1[400005];
ll d[400005],d1[400005];

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 dijkstra2(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<graph1[u].size();i++)
        {
            ll v=graph1[u][i].fi,w=graph1[u][i].se;
            if(d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                pq.push({d[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++)
    {
        ll u,v,w;
        cin >> u >> v >> w;
        u--;v--;
        graph[u].push_back({v,w});
        graph[v].push_back({u,w});
    }
    dijkstra(s);
    dijkstra1(t);
    for(int u=0;u<n;u++)
    {
        graph1[u].push_back({n+u,0});
        graph1[u].push_back({2*n+u,0});
        graph1[n+u].push_back({3*n+u,0});
        graph1[2*n+u].push_back({3*n+u,0});
        for(int i=0;i<graph[u].size();i++)
        {
            ll v=graph[u][i].fi,w=graph[u][i].se;
            if(d[u]+w+d1[v]==d[t])
            {
                graph1[n+u].push_back({n+v,0});
                graph1[2*n+v].push_back({2*n+u,0});
            }
            graph1[u].push_back({v,w});
            graph1[3*n+u].push_back({3*n+v,w});
        }
    }
    dijkstra2(x);
    cout << 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;
}

컴파일 시 표준 에러 (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++)
      |                     ~^~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dijkstra2(ll)':
commuter_pass.cpp:99: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]
   99 |         for(int i=0;i<graph1[u].size();i++)
      |                     ~^~~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:132: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]
  132 |         for(int i=0;i<graph[u].size();i++)
      |                     ~^~~~~~~~~~~~~~~~

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