제출 #1041722

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1041722		vjudge1	Izlet (COI19_izlet)	C++17	0 / 100	706 ms	35700 KiB

izlet

#include<bits/stdc++.h>

using namespace std;

const int N = 3000 + 10;
int c[N][N], n;

void subtask1()
{
  for(int i = 1; i <= n; i ++)
    for(int j = 1; j <= n; j ++)
      c[i][j]--;

  int dist[n + 1], par[n + 1];
  for(int i = 1; i <= n; i ++)
    dist[i] = n + 10, par[i] = -1;
  dist[1] = 0;

  deque<int> Q;
  Q.push_back(1);

  while(Q.size())
    {
      int v = Q.front();
      Q.pop_front();
      for(int u = 1; u <= n; u++)
	{
	  if(u == v) continue;

	  if(dist[v] + c[u][v] < dist[u])
	    {
	      par[u] = v;
	      dist[u] = dist[v] + c[u][v];
	      Q.push_back(u);
	    }
	  else if(dist[u] == dist[v] && !c[u][v] && par[v] != u)
	    par[u] = v;
	}
    }
  for(int i = 1; i <= n; i ++)
    cout << dist[i] % 2 + 1 << ' ';
  cout << endl;

  for(int i = 2; i <= n; i++)
    cout << i << ' ' << par[i] << endl;
}

void subtask2()
{
}

int main()
{
  int t;
  cin >> t >> n;
  for(int i = 1; i <= n; i ++)
    for(int j = 1; j <= n; j ++)
      cin >> c[i][j];
  
  if(t == 1)
    subtask1();
  else
    subtask2();
  return 0;
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 25
• Subtask 3: 0 / 57