Submission #258100

#	Time	Username	Problem	Language	Result	Execution time	Memory
258100		Nicholas_Patrick	Cities (BOI16_cities)	C++17	26 / 100	1876 ms	48368 KiB

cities

// #pragma GCC optimize("O3")
#include <cstdio>
#include <queue>
using namespace std;

int main(){
	int n, k, m;
	scanf("%d%d%d", &n, &k, &m);
	vector <vector <int> > adjLis1(n);
	vector <vector <long long> > disLis1(n);
	vector <int> important(k);
	for(int& i:important){
		scanf("%d", &i);
		i--;
	}
	while(k<4){
		important.push_back(important.back());
		k++;
	}
	for(int i = m;i --;){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		a--;b--;
		adjLis1[a].push_back(b);
		disLis1[a].push_back(c);
		adjLis1[b].push_back(a);
		disLis1[b].push_back(c);
	}
	vector <vector <long long> > multisource(k, vector <long long> (n, 1e14));
	for(int i = 0;i < k;i ++){
		vector <long long>& dist=multisource[i];
		int source=important[i];
		priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
		dist[source]=0ll;
		dijkstra.push(make_pair(dist[source], source));
		while(!dijkstra.empty()){
			int x=dijkstra.top().second;
			long long d=dijkstra.top().first;
			dijkstra.pop();
			if(dist[x]!=d)
				continue;
			for(int i = 0;i < adjLis1[x].size();i ++){
				int y=adjLis1[x][i];
				long long dd=disLis1[x][i];
				if(dist[y]>d+dd){
					dist[y]=d+dd;
					dijkstra.push(make_pair(dist[y], y));
				}
			}
		}
	}
	if(k==5){
		vector <vector <long long> > two;
		int x, y;
		//0 1
		x=0, y=1;
		{
			vector <vector <int> > adjLis2=adjLis1;
			vector <vector <long long> > disLis2=disLis1;
			adjLis2.resize(n+1);
			disLis2.resize(n+1);
			for(int i = 0;i < n;i ++){
				adjLis2[n].push_back(i);
				disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
			}
			int source=n;
			priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
			two.push_back(vector <long long> (n+1, 1e14));
			vector <long long>& dist=two.back();
			dist[source]=0ll;
			dijkstra.push(make_pair(dist[source], source));
			while(!dijkstra.empty()){
				int x=dijkstra.top().second;
				long long d=dijkstra.top().first;
				dijkstra.pop();
				if(dist[x]!=d)
					continue;
				for(int i = 0;i < adjLis2[x].size();i ++){
					int y=adjLis2[x][i];
					long long dd=d+disLis2[x][i];
					if(dist[y]>dd){
						dist[y]=dd;
						dijkstra.push(make_pair(dd, y));
					}
				}
			}
			dist.pop_back();
		}
		//0 2
		x=0, y=2;
		{
			vector <vector <int> > adjLis2=adjLis1;
			vector <vector <long long> > disLis2=disLis1;
			adjLis2.resize(n+1);
			disLis2.resize(n+1);
			for(int i = 0;i < n;i ++){
				adjLis2[n].push_back(i);
				disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
			}
			int source=n;
			priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
			two.push_back(vector <long long> (n+1, 1e14));
			vector <long long>& dist=two.back();
			dist[source]=0ll;
			dijkstra.push(make_pair(dist[source], source));
			while(!dijkstra.empty()){
				int x=dijkstra.top().second;
				long long d=dijkstra.top().first;
				dijkstra.pop();
				if(dist[x]!=d)
					continue;
				for(int i = 0;i < adjLis2[x].size();i ++){
					int y=adjLis2[x][i];
					long long dd=d+disLis2[x][i];
					if(dist[y]>dd){
						dist[y]=dd;
						dijkstra.push(make_pair(dd, y));
					}
				}
			}
			dist.pop_back();
		}
		//0 3
		x=0, y=3;
		{
			vector <vector <int> > adjLis2=adjLis1;
			vector <vector <long long> > disLis2=disLis1;
			adjLis2.resize(n+1);
			disLis2.resize(n+1);
			for(int i = 0;i < n;i ++){
				adjLis2[n].push_back(i);
				disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
			}
			int source=n;
			priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
			two.push_back(vector <long long> (n+1, 1e14));
			vector <long long>& dist=two.back();
			dist[source]=0ll;
			dijkstra.push(make_pair(dist[source], source));
			while(!dijkstra.empty()){
				int x=dijkstra.top().second;
				long long d=dijkstra.top().first;
				dijkstra.pop();
				if(dist[x]!=d)
					continue;
				for(int i = 0;i < adjLis2[x].size();i ++){
					int y=adjLis2[x][i];
					long long dd=d+disLis2[x][i];
					if(dist[y]>dd){
						dist[y]=dd;
						dijkstra.push(make_pair(dd, y));
					}
				}
			}
			dist.pop_back();
		}
		//0 4
		x=0, y=4;
		{
			vector <vector <int> > adjLis2=adjLis1;
			vector <vector <long long> > disLis2=disLis1;
			adjLis2.resize(n+1);
			disLis2.resize(n+1);
			for(int i = 0;i < n;i ++){
				adjLis2[n].push_back(i);
				disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
			}
			int source=n;
			priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
			two.push_back(vector <long long> (n+1, 1e14));
			vector <long long>& dist=two.back();
			dist[source]=0ll;
			dijkstra.push(make_pair(dist[source], source));
			while(!dijkstra.empty()){
				int x=dijkstra.top().second;
				long long d=dijkstra.top().first;
				dijkstra.pop();
				if(dist[x]!=d)
					continue;
				for(int i = 0;i < adjLis2[x].size();i ++){
					int y=adjLis2[x][i];
					long long dd=d+disLis2[x][i];
					if(dist[y]>dd){
						dist[y]=dd;
						dijkstra.push(make_pair(dd, y));
					}
				}
			}
			dist.pop_back();
		}
		//1 2
		x=1, y=2;
		{
			vector <vector <int> > adjLis2=adjLis1;
			vector <vector <long long> > disLis2=disLis1;
			adjLis2.resize(n+1);
			disLis2.resize(n+1);
			for(int i = 0;i < n;i ++){
				adjLis2[n].push_back(i);
				disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
			}
			int source=n;
			priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
			two.push_back(vector <long long> (n+1, 1e14));
			vector <long long>& dist=two.back();
			dist[source]=0ll;
			dijkstra.push(make_pair(dist[source], source));
			while(!dijkstra.empty()){
				int x=dijkstra.top().second;
				long long d=dijkstra.top().first;
				dijkstra.pop();
				if(dist[x]!=d)
					continue;
				for(int i = 0;i < adjLis2[x].size();i ++){
					int y=adjLis2[x][i];
					long long dd=d+disLis2[x][i];
					if(dist[y]>dd){
						dist[y]=dd;
						dijkstra.push(make_pair(dd, y));
					}
				}
			}
			dist.pop_back();
		}
		//1 3
		x=1, y=3;
		{
			vector <vector <int> > adjLis2=adjLis1;
			vector <vector <long long> > disLis2=disLis1;
			adjLis2.resize(n+1);
			disLis2.resize(n+1);
			for(int i = 0;i < n;i ++){
				adjLis2[n].push_back(i);
				disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
			}
			int source=n;
			priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
			two.push_back(vector <long long> (n+1, 1e14));
			vector <long long>& dist=two.back();
			dist[source]=0ll;
			dijkstra.push(make_pair(dist[source], source));
			while(!dijkstra.empty()){
				int x=dijkstra.top().second;
				long long d=dijkstra.top().first;
				dijkstra.pop();
				if(dist[x]!=d)
					continue;
				for(int i = 0;i < adjLis2[x].size();i ++){
					int y=adjLis2[x][i];
					long long dd=d+disLis2[x][i];
					if(dist[y]>dd){
						dist[y]=dd;
						dijkstra.push(make_pair(dd, y));
					}
				}
			}
			dist.pop_back();
		}
		//1 4
		x=1, y=4;
		{
			vector <vector <int> > adjLis2=adjLis1;
			vector <vector <long long> > disLis2=disLis1;
			adjLis2.resize(n+1);
			disLis2.resize(n+1);
			for(int i = 0;i < n;i ++){
				adjLis2[n].push_back(i);
				disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
			}
			int source=n;
			priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
			two.push_back(vector <long long> (n+1, 1e14));
			vector <long long>& dist=two.back();
			dist[source]=0ll;
			dijkstra.push(make_pair(dist[source], source));
			while(!dijkstra.empty()){
				int x=dijkstra.top().second;
				long long d=dijkstra.top().first;
				dijkstra.pop();
				if(dist[x]!=d)
					continue;
				for(int i = 0;i < adjLis2[x].size();i ++){
					int y=adjLis2[x][i];
					long long dd=d+disLis2[x][i];
					if(dist[y]>dd){
						dist[y]=dd;
						dijkstra.push(make_pair(dd, y));
					}
				}
			}
			dist.pop_back();
		}
		//2 3
		x=2, y=3;
		{
			vector <vector <int> > adjLis2=adjLis1;
			vector <vector <long long> > disLis2=disLis1;
			adjLis2.resize(n+1);
			disLis2.resize(n+1);
			for(int i = 0;i < n;i ++){
				adjLis2[n].push_back(i);
				disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
			}
			int source=n;
			priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
			two.push_back(vector <long long> (n+1, 1e14));
			vector <long long>& dist=two.back();
			dist[source]=0ll;
			dijkstra.push(make_pair(dist[source], source));
			while(!dijkstra.empty()){
				int x=dijkstra.top().second;
				long long d=dijkstra.top().first;
				dijkstra.pop();
				if(dist[x]!=d)
					continue;
				for(int i = 0;i < adjLis2[x].size();i ++){
					int y=adjLis2[x][i];
					long long dd=d+disLis2[x][i];
					if(dist[y]>dd){
						dist[y]=dd;
						dijkstra.push(make_pair(dd, y));
					}
				}
			}
			dist.pop_back();
		}
		//2 4
		x=2, y=4;
		{
			vector <vector <int> > adjLis2=adjLis1;
			vector <vector <long long> > disLis2=disLis1;
			adjLis2.resize(n+1);
			disLis2.resize(n+1);
			for(int i = 0;i < n;i ++){
				adjLis2[n].push_back(i);
				disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
			}
			int source=n;
			priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
			two.push_back(vector <long long> (n+1, 1e14));
			vector <long long>& dist=two.back();
			dist[source]=0ll;
			dijkstra.push(make_pair(dist[source], source));
			while(!dijkstra.empty()){
				int x=dijkstra.top().second;
				long long d=dijkstra.top().first;
				dijkstra.pop();
				if(dist[x]!=d)
					continue;
				for(int i = 0;i < adjLis2[x].size();i ++){
					int y=adjLis2[x][i];
					long long dd=d+disLis2[x][i];
					if(dist[y]>dd){
						dist[y]=dd;
						dijkstra.push(make_pair(dd, y));
					}
				}
			}
			dist.pop_back();
		}
		//3 4
		x=3, y=4;
		{
			vector <vector <int> > adjLis2=adjLis1;
			vector <vector <long long> > disLis2=disLis1;
			adjLis2.resize(n+1);
			disLis2.resize(n+1);
			for(int i = 0;i < n;i ++){
				adjLis2[n].push_back(i);
				disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
			}
			int source=n;
			priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
			two.push_back(vector <long long> (n+1, 1e14));
			vector <long long>& dist=two.back();
			dist[source]=0ll;
			dijkstra.push(make_pair(dist[source], source));
			while(!dijkstra.empty()){
				int x=dijkstra.top().second;
				long long d=dijkstra.top().first;
				dijkstra.pop();
				if(dist[x]!=d)
					continue;
				for(int i = 0;i < adjLis2[x].size();i ++){
					int y=adjLis2[x][i];
					long long dd=d+disLis2[x][i];
					if(dist[y]>dd){
						dist[y]=dd;
						dijkstra.push(make_pair(dd, y));
					}
				}
			}
			dist.pop_back();
		}
		long long best=1e14;
		for(int i = 0;i < n;i ++){
			best=min(best, two[0][i]+two[7][i]+multisource[4][i]);
			best=min(best, two[1][i]+two[5][i]+multisource[4][i]);
			best=min(best, two[2][i]+two[4][i]+multisource[4][i]);
			best=min(best, two[0][i]+two[8][i]+multisource[3][i]);
			best=min(best, two[1][i]+two[6][i]+multisource[3][i]);
			best=min(best, two[3][i]+two[4][i]+multisource[3][i]);
			best=min(best, two[0][i]+two[9][i]+multisource[2][i]);
			best=min(best, two[2][i]+two[6][i]+multisource[2][i]);
			best=min(best, two[3][i]+two[5][i]+multisource[2][i]);
			best=min(best, two[1][i]+two[9][i]+multisource[1][i]);
			best=min(best, two[2][i]+two[8][i]+multisource[1][i]);
			best=min(best, two[3][i]+two[7][i]+multisource[1][i]);
			best=min(best, two[4][i]+two[9][i]+multisource[0][i]);
			best=min(best, two[5][i]+two[8][i]+multisource[0][i]);
			best=min(best, two[6][i]+two[7][i]+multisource[0][i]);
		}
		printf("%lld\n", best);
	}
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0;i < adjLis1[x].size();i ++){
                  ~~^~~~~~~~~~~~~~~~~~~
cities.cpp:78:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < adjLis2[x].size();i ++){
                   ~~^~~~~~~~~~~~~~~~~~~
cities.cpp:112:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < adjLis2[x].size();i ++){
                   ~~^~~~~~~~~~~~~~~~~~~
cities.cpp:146:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < adjLis2[x].size();i ++){
                   ~~^~~~~~~~~~~~~~~~~~~
cities.cpp:180:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < adjLis2[x].size();i ++){
                   ~~^~~~~~~~~~~~~~~~~~~
cities.cpp:214:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < adjLis2[x].size();i ++){
                   ~~^~~~~~~~~~~~~~~~~~~
cities.cpp:248:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < adjLis2[x].size();i ++){
                   ~~^~~~~~~~~~~~~~~~~~~
cities.cpp:282:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < adjLis2[x].size();i ++){
                   ~~^~~~~~~~~~~~~~~~~~~
cities.cpp:316:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < adjLis2[x].size();i ++){
                   ~~^~~~~~~~~~~~~~~~~~~
cities.cpp:350:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < adjLis2[x].size();i ++){
                   ~~^~~~~~~~~~~~~~~~~~~
cities.cpp:384:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < adjLis2[x].size();i ++){
                   ~~^~~~~~~~~~~~~~~~~~~
cities.cpp:8:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  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]
   scanf("%d", &i);
   ~~~~~^~~~~~~~~~
cities.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 22
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 26 / 26