oj.uz

Submission #56157

# Submission time Handle Problem Language Result Execution time Memory
56157 2018-07-10T06:32:17 Z 정원준(#1583) Cities (BOI16_cities) C++11
14 / 100
 730 ms 26476 KB 
#include <bits/stdc++.h>
#define L long long
#define inf 8000000000000000000L

using namespace std;

L n,k,m;

vector<L>important;
vector<L>v[100010],l[100010];

struct S{
	L loc,dist;
};

bool operator<(S a,S b){
	return a.dist>b.dist;
}

priority_queue<S>Q;

L dist[5][100010],chk[5][100010];

vector<L> solve3(){
	vector<L>ret(2,0);
	L i,mi=inf,mid;
	for(i=1;i<=n;i++)
	{
		if(dist[0][i]+dist[1][i]+dist[2][i]<mi)
		{
			mi=dist[0][i]+dist[1][i]+dist[2][i];
			mid=i;
		}
	}
	ret[0]=mid;
	ret[1]=mi;
	return ret;
}

int main()
{
	scanf("%lld %lld %lld",&n,&k,&m);
	L i,j;
	for(i=1;i<=k;i++)
	{
		L temp;
		scanf("%lld",&temp);
		important.push_back(temp);
	}
	for(i=1;i<=m;i++)
	{
		L s,e,d;
		scanf("%lld %lld %lld",&s,&e,&d);
		v[s].push_back(e);
		v[e].push_back(s);
		l[s].push_back(d);
		l[e].push_back(d);
	}
	for(i=0;i<k;i++)
	{
		for(j=1;j<=n;j++)
		{
			dist[i][j]=inf;
		}
	}
	for(i=0;i<k;i++)
	{
		dist[i][important[i]]=0;
		Q.push((S){important[i],0});
		while(!Q.empty())
		{
			L x=Q.top().loc;Q.pop();
			if(chk[i][x]) continue;
			chk[i][x]=1;
			for(j=0;j<v[x].size();j++)
			{
				if(dist[i][v[x][j]]>dist[i][x]+l[x][j])
				{
					dist[i][v[x][j]]=dist[i][x]+l[x][j];
					Q.push((S){v[x][j],dist[i][v[x][j]]});
				}
			}
		}
	}
	if(k==2) printf("%lld\n",dist[0][important[1]]);
	else if(k==3)
	{
		printf("%lld\n",solve3()[1]);
	}
	
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:75:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(j=0;j<v[x].size();j++)
            ~^~~~~~~~~~~~
cities.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld",&n,&k,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&temp);
   ~~~~~^~~~~~~~~~~~~~
cities.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld",&s,&e,&d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp: In function 'std::vector<long long int> solve3()':
cities.cpp:35:8: warning: 'mid' may be used uninitialized in this function [-Wmaybe-uninitialized]
  ret[0]=mid;

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 7 ms 5092 KB Output is correct
3 Correct 7 ms 5092 KB Output is correct
4 Incorrect 7 ms 5176 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 580 ms 23420 KB Output is correct
2 Correct 568 ms 23420 KB Output is correct
3 Correct 285 ms 23420 KB Output is correct
4 Correct 133 ms 23420 KB Output is correct
5 Correct 493 ms 23420 KB Output is correct
6 Correct 140 ms 23420 KB Output is correct
7 Correct 10 ms 23420 KB Output is correct
8 Correct 9 ms 23420 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 26.0

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