Logo
(追記) (追記ここまで)

5214번 - 환승 다국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB130003718260827.944%

문제

아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 K개를 서로 연결한다. 1번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개일까?

입력

첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000)

다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어진다. 총 K개 숫자가 주어지며, 이 숫자는 그 하이퍼튜브가 서로 연결하는 역의 번호이다.

출력

첫째 줄에 1번역에서 N번역으로 가는데 방문하는 역의 개수의 최솟값을 출력한다. 만약, 갈 수 없다면 -1을 출력한다.

제한

예제 입력 1 

9 3 5
1 2 3
1 4 5
3 6 7
5 6 7
6 8 9

예제 출력 1 

4

1-3-6-9나 1-5-6-9로 이동하면 된다.

예제 입력 2 

15 8 4
11 12 8 14 13 6 10 7
1 5 8 12 13 6 2 4
10 15 4 5 9 8 14 12
11 12 14 3 5 6 1 13

예제 출력 2 

3

힌트

W3sicHJvYmxlbV9pZCI6IjUyMTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ2NThcdWMyYjkiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzU0NFx1YzhmYyBcdWJhM2MgXHViYmY4XHViNzk4XHVjNWQwIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc3NCBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzc0IFx1YzBhY1x1YzZhOVx1ZDU1OFx1YjI5NCBcdWIzMDBcdWM5MTFcdWFkNTBcdWQxYjVcdWM3NDAgXHVkNTU4XHVjNzc0XHVkMzdjXHVkMjljXHViZTBjXHVjNzc0XHViMmU0LiBcdWQ1NThcdWM3NzRcdWQzN2NcdWQyOWNcdWJlMGMgXHVkNTU4XHViMDk4XHViMjk0IFx1YzVlZCBLXHVhYzFjXHViOTdjIFx1YzExY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWQ1NWNcdWIyZTQuIDFcdWJjODhcdWM1ZWRcdWM1ZDBcdWMxMWMgTlx1YmM4OFx1YzVlZFx1YzczY1x1Yjg1YyBcdWFjMDBcdWIyOTRcdWIzNzAgXHViYzI5XHViYjM4XHVkNTU4XHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWM1ZWRcdWM3NTggXHVjMjE4XHViMjk0IFx1YmE4NyBcdWFjMWNcdWM3N2NcdWFlNGM/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzVlZFx1Yzc1OCBcdWMyMTggTlx1YWNmYyBcdWQ1NWMgXHVkNTU4XHVjNzc0XHVkMzdjXHVkMjljXHViZTBjXHVhYzAwIFx1YzExY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVjNWVkXHVjNzU4IFx1YWMxY1x1YzIxOCBLLCBcdWQ1NThcdWM3NzRcdWQzN2NcdWQyOWNcdWJlMGNcdWM3NTggXHVhYzFjXHVjMjE4IE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMDAsMDAwLCAxICZsZTsgSywgTSAmbGU7IDEwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBNXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1NThcdWM3NzRcdWQzN2NcdWQyOWNcdWJlMGNcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjZDFkIEtcdWFjMWMgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVjNzc0IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWFkZjggXHVkNTU4XHVjNzc0XHVkMzdjXHVkMjljXHViZTBjXHVhYzAwIFx1YzExY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVjNWVkXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yzc3NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIDFcdWJjODhcdWM1ZWRcdWM1ZDBcdWMxMWMgTlx1YmM4OFx1YzVlZFx1YzczY1x1Yjg1YyBcdWFjMDBcdWIyOTRcdWIzNzAgXHViYzI5XHViYjM4XHVkNTU4XHViMjk0IFx1YzVlZFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWFjMDggXHVjMjE4IFx1YzVjNlx1YjJlNFx1YmE3NCAtMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPjEtMy02LTlcdWIwOTggMS01LTYtOVx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjUyMTQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJISVBFUkNJSkVWSSIsImRlc2NyaXB0aW9uIjoiPHA+SW4gYSBnYWxheHkgZmFyLCBmYXIgYXdheSwgdGhlIGZhc3Rlc3QgbWV0aG9kIG9mIHRyYW5zcG9ydGF0aW9uIGlzIHVzaW5nIGh5cGVydHViZXMuIEVhY2ggaHlwZXJ0dWJlIGRpcmVjdGx5IGNvbm5lY3RzIEsgc3RhdGlvbnMgd2l0aCBlYWNoIG90aGVyLiBXaGF0IGlzIHRoZSBtaW5pbXVtIG51bWJlciBvZiBzdGF0aW9ucyB0aGF0IHdlIG5lZWQgdG8gcGFzcyB0aHJvdWdoIGluIG9yZGVyIHRvIGdldCBmcm9tIHN0YXRpb24gMSB0byBzdGF0aW9uIE4/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aHJlZSBwb3NpdGl2ZSBpbnRlZ2VyczogTiAoMSAmbGU7IE4gJmxlOyAxMDAgMDAwKSwgdGhlIG51bWJlciBvZiBzdGF0aW9ucywgSyAoMSAmbGU7IEsgJmxlOyAxIDAwMCksIHRoZSBudW1iZXIgb2Ygc3RhdGlvbnMgdGhhdCBhbnkgc2luZ2xlIGh5cGVydHViZSBkaXJlY3RseSBpbnRlcmNvbm5lY3RzLCBhbmQgTSAoMSAmbGU7IE0gJmxlOyAxIDAwMCksIHRoZSBudW1iZXIgb2YgaHlwZXJ0dWJlcy48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE0gbGluZXMgY29udGFpbnMgdGhlIGRlc2NyaXB0aW9uIG9mIGEgc2luZ2xlIGh5cGVydHViZTogSyBwb3NpdGl2ZSBpbnRlZ2VycywgdGhlIGxhYmVscyBvZiBzdGF0aW9ucyBjb25uZWN0ZWQgdG8gdGhhdCBoeXBlcnR1YmUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgcmVxdWlyZWQgbWluaW11bSBudW1iZXIgb2Ygc3RhdGlvbnMuIElmIGl0IGlzbiYjMzk7dCBwb3NzaWJsZSB0byB0cmF2ZWwgZnJvbSBzdGF0aW9uIDEgdG8gc3RhdGlvbiBOLCBvdXRwdXQgLTEuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsInNhbXBsZV9leHBsYWluXzEiOiI8cD5JdCBpcyBwb3NzaWJsZSB0byB0cmF2ZWwgZnJvbSBzdGF0aW9uIDEgdG8gc3RhdGlvbiA5IHVzaW5nIG9ubHkgZm91ciBzdGF0aW9ucyBpbiB0aGUgZm9sbG93aW5nIHdheXM6IDEtMy02LTksIG9yIDEtNS02LTkuPFwvcD5cclxuIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #5 4번

(追記) (追記ここまで)

출처

대학교 대회

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

AltStyle によって変換されたページ (->オリジナル) /