제출 #59275

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59275		TadijaSebez	악어의 지하 도시 (IOI11_crocodile)	C++11	100 / 100	1044 ms	99840 KiB

crocodile

#include "crocodile.h"
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
const int N=100050;
const int M=1000050;
const ll inf=1e18;
ll fir[N],sec[N];
vector<pair<int,int> > E[N];
int disc[N],tid;
bool mark[N];
void DFS(int u)
{
	disc[u]=++tid;
	if(mark[u]){ fir[u]=sec[u]=0;return;}
	for(int i=0;i<E[u].size();i++)
	{
		int v=E[u][i].first;
		int w=E[u][i].second;
		if(!disc[v]) DFS(v);
		if(disc[v]>disc[u] || mark[v])
		{
			if(fir[u]>sec[v]+w) sec[u]=fir[u],fir[u]=sec[v]+w;
			else if(sec[u]>sec[v]+w) sec[u]=sec[v]+w;
		}
	}
}
void AddEdge(int u, int v, int w){ E[u].pb(mp(v,w));E[v].pb(mp(u,w));}
bool was[N];
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
	int i;
	for(i=0;i<m;i++) AddEdge(r[i][0]+1,r[i][1]+1,l[i]);
	for(i=0;i<k;i++) mark[p[i]+1]=1;
	for(i=1;i<=n;i++) fir[i]=sec[i]=inf;
	//DFS(1);
	priority_queue<pair<ll,int> > pq;
	for(i=1;i<=n;i++) if(mark[i])
	{
		pq.push(mp(0,i));
		fir[i]=sec[i]=0;
	}
	while(pq.size())
	{
		int u=pq.top().second;
		pq.pop();
		if(was[u]) continue;
		was[u]=1;
		for(int i=0;i<E[u].size();i++)
		{
			int v=E[u][i].first;
			int w=E[u][i].second;
			if(sec[u]+w<fir[v])
			{
				sec[v]=fir[v];
				fir[v]=sec[u]+w;
				pq.push(mp(-sec[v],v));
			}
			else if(sec[u]+w<sec[v])
			{
				sec[v]=sec[u]+w;
				pq.push(mp(-sec[v],v));
			}
		}
	}
	return sec[1];
}
/*int r[M][2],l[M],p[N];
int main()
{
	int n,m,k,i;
	scanf("%i %i %i",&n,&m,&k);
	for(i=0;i<m;i++) scanf("%i %i %i",&r[i][0],&r[i][1],&l[i]);
	for(i=0;i<k;i++) scanf("%i",&p[i]);
	printf("%i\n",travel_plan(n,m,r,l,k,p));
	return 0;
}*/

컴파일 시 표준 에러 (stderr) 메시지

crocodile.cpp: In function 'void DFS(int)':
crocodile.cpp:21:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<E[u].size();i++)
              ~^~~~~~~~~~~~
crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:54:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<E[u].size();i++)
               ~^~~~~~~~~~~~

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11