Submission #00375

ソースコード

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define RREP(i,a,b) for(int i=(a);i>=(b);i--)
#define pq priority_queue
#define P pair<ll,ll>
#define P2 pair<int,P>
#define P3 pair<int,P2>
typedef long long ll; typedef long double ld;
using namespace std;
const int INF=1e9, MOD=1e9+7, around[]={0,1,1,-1,-1,0,-1,1,0,0};
const ll LINF=1e18;
const ld PI=abs(acos(-1));
int n,m,a,b,v,u; ll w;
ll lia[100010]={},lib[100010]={},li[100010];
vector<P> g[100010];
set<int> sta;
 
ll dijkstra(int s, int t, bool f){
        ll min_cost[100010]={}; ll mi=LINF;
        pq<P, vector<P>, greater<P>> que;
        REP(i,0,n) min_cost[i]=LINF;
        que.emplace(0,s);
        min_cost[s]=0;
        while(!que.empty()){
                auto p=que.top(); que.pop();
                if(p.first>min_cost[p.second]) continue;
                 
                for(auto e:g[p.second]){
                        if(p.first+e.second>=min_cost[e.first]) continue;
                        min_cost[e.first]=p.first+e.second;
                        if(sta.count(e.first)) mi=min(mi,min_cost[e.first]);
                        que.emplace(min_cost[e.first], e.first);
                }
        }
         
        return (f?mi:min_cost[t]);
}
 
ll find(int s, bool f){
        ll min_cost[100010]={};
        pq<P, vector<P>, greater<P>> que;
        REP(i,0,n) min_cost[i]=LINF;
        que.emplace(0,s);
        min_cost[s]=0;
        while(!que.empty()){
                auto p=que.top(); que.pop();
                if(p.first>min_cost[p.second]) continue;
                 
                for(auto e:g[p.second]){
                        if(p.first+e.second>=min_cost[e.first]) continue;
                        min_cost[e.first]=p.first+e.second;
                        que.emplace(min_cost[e.first], e.first);
                }
        }
         
        if(f) REP(i,0,n) lia[i]=min_cost[i];
        else REP(i,0,n) lib[i]=min_cost[i];
        return 0;
}
 
int make(int s){
        ll min_cost[100010]={};
        pq<P, vector<P>, greater<P>> que;
        REP(i,0,n) min_cost[i]=LINF;
        que.emplace(0,s);
        min_cost[s]=0;
        while(!que.empty()){
                auto p=que.top(); que.pop();
                if(p.first>li[p.second]) continue;
                li[p.second]=min(li[p.second], p.first);
                 
                for(auto e:g[p.second]){
                        if(p.first+e.second>=li[e.first]) continue;
                        min_cost[e.first]=p.first+e.second;
                        que.emplace(min_cost[e.first], e.first);
                }
        }
         
        return 0;
}
 
int main(){
        cin >> n >> m >> a >> b; a--; b--;
        REP(i,0,m){
                scanf("%d %d %lld",&v,&u,&w);
                g[u-1].push_back(P(v-1,w));
                g[v-1].push_back(P(u-1,w));
        }
         
        ll s=0; bool f=true;
        set<int> vv;
        find(a,1); find(b,0); ll minc=lia[b];
        REP(i,0,n) if(minc==lia[i]+lib[i]) sta.insert(i);
        REP(i,0,n) li[i]=LINF;
        for(auto s:sta) make(s);
        REP(i,0,n) s+=li[i];
        cout << s << endl;
        return 0;
}

ステータス

項目	データ
問題	0004 - railway
ユーザー名	Noel
投稿日時	2017-11-26 14:55:48
言語	C++11
状態	Accepted
得点	100
ソースコード長	2478 Byte
最大実行時間	305 ms
最大メモリ使用量	19664 KB

セット

	セット	得点	Cases
1	ALL	80 / 80	*
2	partial_1	20 / 20	!, S*

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
!test01.txt	AC	18 ms	5344 KB	1	2
!test02.txt	AC	25 ms	5320 KB	1	2
mesh_01.txt	AC	92 ms	18464 KB	1
mesh_02.txt	AC	96 ms	19624 KB	1
randomL_01.txt	AC	305 ms	19564 KB	1
randomL_02.txt	AC	286 ms	19632 KB	1
randomL_03.txt	AC	242 ms	19560 KB	1
randomL_04.txt	AC	276 ms	19664 KB	1
randomL_05.txt	AC	279 ms	19532 KB	1
randomS_01.txt	AC	25 ms	5436 KB	1	2
randomS_02.txt	AC	16 ms	5512 KB	1	2
randomS_03.txt	AC	21 ms	5468 KB	1	2
treeL_01.txt	AC	193 ms	11060 KB	1
treeL_02.txt	AC	188 ms	11180 KB	1
treeS_01.txt	AC	25 ms	5416 KB	1	2
treeS_02.txt	AC	23 ms	5348 KB	1	2