oj.uz

Submission #66807

# Submission time Handle Problem Language Result Execution time Memory
66807 2018-08-12T10:33:17 Z quoriess Commuter Pass (JOI18_commuter_pass) C++14
0 / 100
 783 ms 19724 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef pair<lli,lli> pii;
vector<vector<pii> > adj;
void dijk(int start,vector<lli>& dist,vector<lli>& pre){
	set<pii> nodes;
	int len=dist.size();
	dist=vector<lli>(len,1e17);
	nodes.insert(pii(0,start));
	dist[start]=0;
	pre=vector<lli>(len,-1);
	while(!nodes.empty())
	{
		auto sim=*nodes.begin();		
		nodes.erase(sim);
		for(auto u:adj[sim.second]){
			if(dist[sim.second]+u.second<dist[u.first]){
				if(nodes.find(pii(dist[u.first],u.first))!=nodes.end())
					nodes.erase(pii(dist[u.first],u.first));
				dist[u.first]=dist[sim.second]+u.second;
				pre[u.first]=sim.second;
				nodes.insert(pii(dist[u.first],u.first));
			}
		}
	}
	
}
/*
5 7
1 3
1 5
1 2 1
2 3 3
1 3 2
3 4 1
3 5 2
1 4 1
1 5 7 
 * */
int main(){
	int n,m;
	cin>>n>>m;
	lli s,t,u,v;
	cin>>s>>t>>u>>v;
	adj=vector<vector<pii> >(n+1,vector<pii>());
	for (int i = 0; i < m; i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		adj[a].push_back(pii(b,c));
		adj[b].push_back(pii(a,c));
	}
	vector<lli> distS(n+1),preS(n+1);
	dijk(s,distS,preS);
	
	vector<lli> distv(n+1),prev(n+1);
	
	dijk(v,distv,prev);
	lli snc=1e17;
	for (int i = t; i != -1 ; i=preS[i])
	{
		//cout <<"i: "<<i<<"\n";
		snc=min(distv[i],snc);
	}
	cout << snc<<"\n";
	return 0;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 732 ms 19208 KB Output is correct
2 Correct 705 ms 19208 KB Output is correct
3 Correct 696 ms 19208 KB Output is correct
4 Incorrect 775 ms 19724 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 783 ms 19724 KB Output is correct
2 Correct 703 ms 19724 KB Output is correct
3 Incorrect 778 ms 19724 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

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

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 732 ms 19208 KB Output is correct
2 Correct 705 ms 19208 KB Output is correct
3 Correct 696 ms 19208 KB Output is correct
4 Incorrect 775 ms 19724 KB Output isn't correct
5 Halted 0 ms 0 KB -