oj.uz

답안 #395304

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
395304 2021-04-28T06:19:36 Z jansenkenpegrasio Cities (BOI16_cities) C++14
14 / 100
 280 ms 16428 KB 
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int main()
{
	int n,k,m;
	scanf("%d%d%d",&n,&k,&m);
	int important[k+5];
	vector< pair< int,int > > adjLis[n+5];
	for(int i=1;i<=k;i++)
		scanf("%d",& important[i]);
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		adjLis[a].push_back(make_pair(b,c));
		adjLis[b].push_back(make_pair(a,c));
	}
	if(k==2)
	{
		priority_queue< pair<long long,int> >djikstra;
		long long distance[n+5];
		fill(distance,distance+n+5,100000000000000);
		distance[important[1]]=0;
		djikstra.push(make_pair(0,important[1]));
		while(djikstra.empty()==false)
		{
			long long jarak = -djikstra.top().first;
			int asal = djikstra.top().second;
			djikstra.pop();
			if(distance[asal]!=jarak)
				continue;
			for(int x=0;x<adjLis[asal].size();x++)
			{
				int tujuan = adjLis[asal][x].first;
				long long biaya = jarak + adjLis[asal][x].second;
				if(distance[tujuan]>biaya)
				{
					djikstra.push(make_pair(-biaya,tujuan));
					distance[tujuan]=biaya;
				}
			}
		}
		printf("%lld",distance[important[2]]);
	}
	else if(k==3)
	{
/*		
		int terdekat;
		for(int a=0;a<adjLis[important[1]].size();a++)
			for(int b=0;b<adjLis[important[2]].size();b++)
				for(int c=0;c<adjLis[important[3]].size();c++)
					if(adjLis[important[1]][a].first==adjLis[important[2]][b].first && adjLis[important[2]][b].first==adjLis[important[3]][c].first)
						terdekat = adjLis[important[1]][a].first;
*/						
//		long long total=0;
		priority_queue< pair<long long,int> >djikstra;
		long long distance1[n+5];
		fill(distance1,distance1+n+5,100000000000000);
		distance1[important[1]]=0;
		djikstra.push(make_pair(0,important[1]));
		while(djikstra.empty()==false)
		{
			long long jarak = -djikstra.top().first;
			int asal = djikstra.top().second;
			djikstra.pop();
			if(distance1[asal]!=jarak)
				continue;
			for(int x=0;x<adjLis[asal].size();x++)
			{
				int tujuan = adjLis[asal][x].first;
				long long biaya = jarak + adjLis[asal][x].second;
				if(distance1[tujuan]>biaya)
				{
					djikstra.push(make_pair(-biaya,tujuan));
					distance1[tujuan]=biaya;
				}
			}
		}
//		total=total+distance[terdekat];
		long long distance2[n+5];
		fill(distance2,distance2+n+5,100000000000000);
//		distance2[terdekat]=0;
		distance2[important[2]]=0;
		djikstra.push(make_pair(0,important[2]));
		while(djikstra.empty()==false)
		{
			long long jarak = -djikstra.top().first;
			int asal = djikstra.top().second;
			djikstra.pop();
			if(distance2[asal]!=jarak)
				continue;
			for(int x=0;x<adjLis[asal].size();x++)
			{
				int tujuan = adjLis[asal][x].first;
				long long biaya = jarak + adjLis[asal][x].second;
				if(distance2[tujuan]>biaya)
				{
					djikstra.push(make_pair(-biaya,tujuan));
					distance2[tujuan]=biaya;
				}
			}
		}
//		total=total+distance[terdekat];
//		distance[terdekat]=0;
		long long distance3[n+5];
		fill(distance3,distance3+n+5,100000000000000);
		distance3[important[3]]=0;
		djikstra.push(make_pair(0,important[3]));
		while(djikstra.empty()==false)
		{
			long long jarak = -djikstra.top().first;
			int asal = djikstra.top().second;
			djikstra.pop();
			if(distance3[asal]!=jarak)
				continue;
			for(int x=0;x<adjLis[asal].size();x++)
			{
				int tujuan = adjLis[asal][x].first;
				long long biaya = jarak + adjLis[asal][x].second;
				if(distance3[tujuan]>biaya)
				{
					djikstra.push(make_pair(-biaya,tujuan));
					distance3[tujuan]=biaya;
				}
			}
		}
//		total=total+distance[terdekat];
//		printf("%lld\n",total);
		long long minimum = 1000000000000000;
/*
		printf("Isi distance[1]\n");
		for(int a=1;a<=n;a++)
			printf("%lld ", distance1[a]);
		printf("\n");
		
		printf("Isi distance[2]\n");
		for(int a=1;a<=n;a++)
			printf("%lld ", distance2[a]);
		printf("\n");
		
		printf("Isi distance[3]\n");
		for(int a=1;a<=n;a++)
			printf("%lld ", distance3[a]);
		printf("\n");
*/
		for(int a=1;a<=n;a++)
			if(distance1[a]>0 && distance2[a]>0 && distance3[a]>0)
				minimum = min(minimum, distance1[a]+distance2[a]+distance3[a]);
		printf("%lld",minimum);
	}
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:35:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |    for(int x=0;x<adjLis[asal].size();x++)
      |                ~^~~~~~~~~~~~~~~~~~~~
cities.cpp:71:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |    for(int x=0;x<adjLis[asal].size();x++)
      |                ~^~~~~~~~~~~~~~~~~~~~
cities.cpp:95:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |    for(int x=0;x<adjLis[asal].size();x++)
      |                ~^~~~~~~~~~~~~~~~~~~~
cities.cpp:119:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |    for(int x=0;x<adjLis[asal].size();x++)
      |                ~^~~~~~~~~~~~~~~~~~~~
cities.cpp:9:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    9 |  scanf("%d%d%d",&n,&k,&m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
cities.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   13 |   scanf("%d",& important[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~
cities.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |   scanf("%d%d%d",&a,&b,&c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 259 ms 16324 KB Output is correct
2 Correct 280 ms 16428 KB Output is correct
3 Correct 134 ms 10172 KB Output is correct
4 Correct 78 ms 8436 KB Output is correct
5 Correct 171 ms 14908 KB Output is correct
6 Correct 86 ms 8308 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 137 ms 13044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 139 ms 12952 KB Output isn't correct
2 Halted 0 ms 0 KB -