oj.uz

Submission #41703

# Submission time Handle Problem Language Result Execution time Memory
41703 2018-02-21T01:19:57 Z wzy Ferries (NOI13_ferries) C++11
17 / 40
 822 ms 32768 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define pb push_back
#define F first
#define S second
int fx[100005] , n , m;
vector<int> adj[100005] ;
vector<pii>  radj[100005];
vector<int> p[100005];

bool cmp(int i , int j){
	if(fx[i] == fx[j]) return i;
	else{
		return fx[i] > fx[j];
	}
}


int32_t main(){
	scanf("%lld%lld" , &n , &m);
	vector<pii> edges;
	for(int i = 0 ; i < m ; i++){
		int x, y,z;
		cin>>x>>y>>z;
		x--, y--;
		p[x].pb(z);
		adj[x].pb(y);
		edges.pb(pii(x,y));
	}
	for(int i = 0 ; i < n;i++) sort(p[i].begin() , p[i].end()), fx[i] = (int) 1e18;
	for(int i =0;i<m;i++){
		radj[edges[i].S].pb(pii(p[edges[i].F][0] , edges[i].F));
	}
	priority_queue<pii , vector<pii> , greater<pii> > pq;
	fx[n-1] = 0;
	pq.push(pii(0 , n-1));
	while(!pq.empty()){
		pii u = pq.top();
		pq.pop();
		if(fx[u.S] != u.F) continue;
		for(int j = 0 ; j < radj[u.S].size(); j++){
			pii v = radj[u.S][j];
			if(fx[v.S] > v.F + u.F){
				fx[v.S] = v.F + u.F;
				pq.push(pii(fx[v.S] , v.S));
			}
		}
	}
	for(int i = 0 ; i < n;i++){
		sort(adj[i].begin() , adj[i].end() , cmp);
	}
	for(int i = 0 ; i < n; i++) fx[i] = (int) 1e18;
	fx[0] = 0;
	pq.push(pii(0 , 0));
	while(!pq.empty()){
		pii u = pq.top();
		pq.pop();
		if(fx[u.S] != u.F) continue;
		for(int j = 0 ; j < adj[u.S].size() ;j++){
			pii v = pii(p[u.S][j] , adj[u.S][j]);
			if(fx[v.S] > v.F + u.F){
				fx[v.S] = v.F + u.F;
				pq.push(pii(fx[v.S] , v.S));
			}
		}
	}
	printf("%lld\n" , fx[n-1]);
}

Compilation message

ferries.cpp: In function 'int32_t main()':
ferries.cpp:43:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0 ; j < radj[u.S].size(); j++){
                     ^
ferries.cpp:61:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0 ; j < adj[u.S].size() ;j++){
                     ^
ferries.cpp:22:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld" , &n , &m);
                             ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7288 KB Output is correct
2 Correct 13 ms 7652 KB Output is correct
3 Correct 36 ms 10076 KB Output is correct
4 Correct 339 ms 31036 KB Output is correct
5 Correct 372 ms 32768 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 32768 KB Output is correct
2 Correct 11 ms 32768 KB Output is correct
3 Correct 38 ms 32768 KB Output is correct
4 Correct 154 ms 32768 KB Output is correct
5 Correct 286 ms 32768 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 32768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 822 ms 32768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -