oj.uz

답안 #41276

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
41276 2018-02-15T10:36:24 Z Kerim Commuter Pass (JOI18_commuter_pass) C++14
40 / 100
 2000 ms 17476 KB 
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int n,m,u,v,s,t;
vector<PII>adj[MAXN];
const ll B=1e15;
ll dis[MAXN],d1[MAXN],d2[MAXN],dp[MAXN];
ll dp1[MAXN],dp2[MAXN],d3[MAXN],d4[MAXN];
void bfs(int st){
	for(int i=1;i<=n;i++)
		dis[i]=B;
	//~ priority_queue<PII,vector<PII>,greater<PII> >q;	
	queue<PII>q;
	q.push(mp(0,st));dis[st]=0;
	while(!q.empty()){
		int nd=q.front().ss;q.pop();
		tr(it,adj[nd])
			if(umin(dis[it->ff],dis[nd]+it->ss))
				q.push(mp(dis[it->ff],it->ff));
	}
}
void kfs(int st){
	for(int i=1;i<=n;i++)
		dis[i]=B,dp[i]=B;
	priority_queue<PII,vector<PII>,greater<PII> >q;	
	q.push(mp(0,st));dis[st]=0;dp[st]=d2[st];
	while(!q.empty()){
		int nd=q.top().ss;q.pop();
		tr(it,adj[nd])
			if(dis[it->ff]>dis[nd]+it->ss){
				dis[it->ff]=dis[nd]+it->ss;
				q.push(mp(dis[it->ff],it->ff));
				dp[it->ff]=min(dp[nd],d2[it->ff]);
			}
			else if(dis[it->ff]==dis[nd]+it->ss){
				//~ q.push(it->ff);
				umin(dp[it->ff],min(dp[nd],d2[it->ff]));
			}
	}
}
int main(){
    //~ freopen("file.in", "r", stdin);
    scanf("%d%d%d%d%d%d",&n,&m,&s,&t,&u,&v);
    while(m--){
		int uu,vv,w;
		scanf("%d%d%d",&uu,&vv,&w);
		adj[uu].pb(mp(vv,w));
		adj[vv].pb(mp(uu,w));
	}
	bfs(u);for(int i=1;i<=n;i++)d1[i]=dis[i];
	bfs(v);for(int i=1;i<=n;i++)d2[i]=dis[i];
	bfs(s);for(int i=1;i<=n;i++)d3[i]=dis[i];
	bfs(t);for(int i=1;i<=n;i++)d4[i]=dis[i];
	kfs(s);for(int i=1;i<=n;i++)dp1[i]=dp[i];
	kfs(t);for(int i=1;i<=n;i++)dp2[i]=dp[i];
	ll ans=d1[v];
	for(int i=1;i<=n;i++)
		if(d3[i]+d4[i]==d3[t])
			umin(ans,d1[i]+min(dp1[i],dp2[i]));
	printf("%lld\n",ans);		
	return 0;
}

Compilation message

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:59:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d%d%d",&n,&m,&s,&t,&u,&v);
                                            ^
commuter_pass.cpp:62:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&uu,&vv,&w);
                             ^

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 480 ms 16104 KB Output is correct
2 Correct 812 ms 16104 KB Output is correct
3 Correct 925 ms 16360 KB Output is correct
4 Correct 368 ms 16360 KB Output is correct
5 Correct 692 ms 16360 KB Output is correct
6 Correct 467 ms 16536 KB Output is correct
7 Correct 950 ms 16536 KB Output is correct
8 Correct 897 ms 16536 KB Output is correct
9 Correct 847 ms 17476 KB Output is correct
10 Correct 633 ms 17476 KB Output is correct
11 Correct 138 ms 17476 KB Output is correct
12 Correct 804 ms 17476 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2047 ms 17476 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 17476 KB Output is correct
2 Correct 4 ms 17476 KB Output is correct
3 Correct 4 ms 17476 KB Output is correct
4 Correct 22 ms 17476 KB Output is correct
5 Correct 14 ms 17476 KB Output is correct
6 Correct 4 ms 17476 KB Output is correct
7 Correct 4 ms 17476 KB Output is correct
8 Correct 6 ms 17476 KB Output is correct
9 Correct 4 ms 17476 KB Output is correct
10 Correct 14 ms 17476 KB Output is correct
11 Correct 4 ms 17476 KB Output is correct
12 Correct 4 ms 17476 KB Output is correct
13 Correct 4 ms 17476 KB Output is correct
14 Correct 4 ms 17476 KB Output is correct
15 Correct 4 ms 17476 KB Output is correct

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 480 ms 16104 KB Output is correct
2 Correct 812 ms 16104 KB Output is correct
3 Correct 925 ms 16360 KB Output is correct
4 Correct 368 ms 16360 KB Output is correct
5 Correct 692 ms 16360 KB Output is correct
6 Correct 467 ms 16536 KB Output is correct
7 Correct 950 ms 16536 KB Output is correct
8 Correct 897 ms 16536 KB Output is correct
9 Correct 847 ms 17476 KB Output is correct
10 Correct 633 ms 17476 KB Output is correct
11 Correct 138 ms 17476 KB Output is correct
12 Correct 804 ms 17476 KB Output is correct
13 Execution timed out 2047 ms 17476 KB Time limit exceeded
14 Halted 0 ms 0 KB -