시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB182946631623.813%

문제

n(1 ≤ n ≤ 100)개의 섬이 m(1 ≤ m ≤ 1,000)개의 다리로 연결되어 있다. 각각의 다리는 서로 다른 두 섬을 연결하고 있으며, 서로 다른 두 섬은 최대 한 개의 다리로만 직접 연결되어 있다. 각각의 다리들의 튼튼한 정도는 서로 달라서, 각각의 다리마다 견딜 수 있는 무게의 제한이 다를 수 있다.

섬들 중, K(1 ≤ K ≤ 14)개의 서로 다른 섬에 각각 한 개씩 보석이 있다. 당신은 1번 섬에서 빈손으로 출발하여 최대한 많은 보석을 줍고 1번 섬으로 돌아오려 한다. 주의할 것은, 보석을 너무 많이 줍다 보면 다리를 건널 때 다리가 무게를 견디지 못하고 무너질 수 있다는 점이다. 따라서 당신은 다리가 무너지지 않는 한도 내에서 보석을 주워야 한다.

한 번 지난 적이 있는 다리와 섬을 여러 번 지날 수 있으며, 보석이 있는 섬을 지날 때에 그 보석을 줍지 않을 수도 있다고 하자.

입력

첫째 줄에 n, m, K가 주어진다. 다음 K개의 줄에는 보석이 있는 섬의 번호가 주어진다. 다음 m개의 줄에는 각 다리에 대한 정보를 나타내는 세 자연수 a, b, c(1 ≤ c ≤ 100)가 주어진다. 이는 a번 섬과 b번 섬이 다리로 연결되어 있는데, 그 다리가 최대 c개의 보석만을 견딜 수 있다는 의미이다. 예를 들어 c가 2라면, 그 다리를 지날 때 보석을 0, 1, 2개 가지고 있어야 한다는 의미이다. 3개 이상의 보석을 가지고 그 다리를 지나려고 하면 다리가 무너진다.

출력

첫째 줄에 주울 수 있는 보석의 최대 개수를 출력한다.

예제 입력 1

6 7 5
1
2
3
4
5
1 2 3
3 6 2
6 2 10
2 4 1
5 1 1
4 5 1
1 6 1

예제 출력 1

4
W3sicHJvYmxlbV9pZCI6IjIwMDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjZjRcdWMxMWQgXHVjOTBkXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5uKDEgJmxlOyBuJm5ic3A7JmxlOyAxMDApXHVhYzFjXHVjNzU4IFx1YzEyY1x1Yzc3NCBtKDEgJmxlOyBtICZsZTsgMSwwMDApXHVhYzFjXHVjNzU4IFx1YjJlNFx1YjlhY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHViMmU0XHViOWFjXHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViNDUwIFx1YzEyY1x1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWFjZTAgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YjQ1MCBcdWMxMmNcdWM3NDAgXHVjZDVjXHViMzAwIFx1ZDU1YyBcdWFjMWNcdWM3NTggXHViMmU0XHViOWFjXHViODVjXHViOWNjIFx1YzljMVx1YzgxMSBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHViMmU0XHViOWFjXHViNGU0XHVjNzU4IFx1ZDJiY1x1ZDJiY1x1ZDU1YyBcdWM4MTVcdWIzYzRcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlY1x1Yjc3Y1x1YzExYywgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YjJlNFx1YjlhY1x1YjljOFx1YjJlNCBcdWFjYWNcdWI1MWMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJiMzRcdWFjOGNcdWM3NTggXHVjODFjXHVkNTVjXHVjNzc0IFx1YjJlNFx1Yjk3YyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMmNcdWI0ZTQgXHVjOTExLCBLKDEgJmxlOyBLICZsZTsgMTQpXHVhYzFjXHVjNzU4IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjMTJjXHVjNWQwIFx1YWMwMVx1YWMwMSBcdWQ1NWMgXHVhYzFjXHVjNTI5IFx1YmNmNFx1YzExZFx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YjJmOVx1YzJlMFx1Yzc0MCAxXHViYzg4IFx1YzEyY1x1YzVkMFx1YzExYyBcdWJlNDhcdWMxOTBcdWM3M2NcdWI4NWMgXHVjZDljXHViYzFjXHVkNTU4XHVjNWVjIFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWI5Y2VcdWM3NDAgXHViY2Y0XHVjMTFkXHVjNzQ0IFx1YzkwZFx1YWNlMCAxXHViYzg4IFx1YzEyY1x1YzczY1x1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2MjRcdWI4MjQgXHVkNTVjXHViMmU0LiBcdWM4ZmNcdWM3NThcdWQ1NjAgXHVhYzgzXHVjNzQwLCBcdWJjZjRcdWMxMWRcdWM3NDQgXHViMTA4XHViYjM0IFx1YjljZVx1Yzc3NCBcdWM5MGRcdWIyZTQgXHViY2Y0XHViYTc0IFx1YjJlNFx1YjlhY1x1Yjk3YyBcdWFjNzRcdWIxMTAgXHViNTRjIFx1YjJlNFx1YjlhY1x1YWMwMCBcdWJiMzRcdWFjOGNcdWI5N2MgXHVhY2FjXHViNTE0XHVjOWMwIFx1YmFiYlx1ZDU1OFx1YWNlMCBcdWJiMzRcdWIxMDhcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWM4MTBcdWM3NzRcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWIyZjlcdWMyZTBcdWM3NDAgXHViMmU0XHViOWFjXHVhYzAwIFx1YmIzNFx1YjEwOFx1YzljMFx1YzljMCBcdWM1NGFcdWIyOTQgXHVkNTVjXHViM2M0IFx1YjBiNFx1YzVkMFx1YzExYyBcdWJjZjRcdWMxMWRcdWM3NDQgXHVjOGZjXHVjNmNjXHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTVjIFx1YmM4OCBcdWM5YzBcdWIwOWMgXHVjODAxXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWIyZTRcdWI5YWNcdWM2NDAgXHVjMTJjXHVjNzQ0IFx1YzVlY1x1YjdlYyBcdWJjODggXHVjOWMwXHViMGEwIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YmNmNFx1YzExZFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVjMTJjXHVjNzQ0IFx1YzljMFx1YjBhMCBcdWI1NGNcdWM1ZDAgXHVhZGY4IFx1YmNmNFx1YzExZFx1Yzc0NCBcdWM5MGRcdWM5YzAgXHVjNTRhXHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTRcdWFjZTAgXHVkNTU4XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBuLCBtLCBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIEtcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmNmNFx1YzExZFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVjMTJjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBtXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHViMmU0XHViOWFjXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM4MTVcdWJjZjRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzEzOCBcdWM3OTBcdWM1ZjBcdWMyMTggYSwgYiwgYygxICZsZTsgYyAmbGU7IDEwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWIyOTQgYVx1YmM4OCBcdWMxMmNcdWFjZmMgYlx1YmM4OCBcdWMxMmNcdWM3NzQgXHViMmU0XHViOWFjXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1YWRmOCBcdWIyZTRcdWI5YWNcdWFjMDAgXHVjZDVjXHViMzAwIGNcdWFjMWNcdWM3NTggXHViY2Y0XHVjMTFkXHViOWNjXHVjNzQ0IFx1YWNhY1x1YjUxYyBcdWMyMTggXHVjNzg4XHViMmU0XHViMjk0IFx1Yzc1OFx1YmJmOFx1Yzc3NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBjXHVhYzAwIDJcdWI3N2NcdWJhNzQsIFx1YWRmOCBcdWIyZTRcdWI5YWNcdWI5N2MgXHVjOWMwXHViMGEwIFx1YjU0YyBcdWJjZjRcdWMxMWRcdWM3NDQgMCwgMSwgMlx1YWMxYyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNFx1YjI5NCBcdWM3NThcdWJiZjhcdWM3NzRcdWIyZTQuIDNcdWFjMWMgXHVjNzc0XHVjMGMxXHVjNzU4IFx1YmNmNFx1YzExZFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVhZGY4IFx1YjJlNFx1YjlhY1x1Yjk3YyBcdWM5YzBcdWIwOThcdWI4MjRcdWFjZTAgXHVkNTU4XHViYTc0IFx1YjJlNFx1YjlhY1x1YWMwMCBcdWJiMzRcdWIxMDhcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4ZmNcdWM2YjggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJjZjRcdWMxMWRcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjAwMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNhdmUgQ293cyAxIiwiZGVzY3JpcHRpb24iOiI8cD5GZXcgcGVvcGxlIGtub3cgdGhhdCBjb3dzIGFyZSBhY3R1YWxseSBxdWl0ZSBmb25kIG9mIGV4cGxvcmluZyBjYXZlcy4gJm5ic3A7PFwvcD5cclxuXHJcbjxwPkJlc3NpZSBpcyBwbGFubmluZyB0byB2aXNpdCBoZXIgZmF2b3JpdGUgY2F2ZSwgd2hpY2ggaGFzIE4gcm9vbXMgKDEgJmx0Oz0gTiAmbHQ7PSAxMDApIG51bWJlcmVkIDEuLk4gYW5kIE0gYmlkaXJlY3Rpb25hbCBjb3JyaWRvcnMgKDEgJmx0Oz0gTSAmbHQ7PSAxMDAwKSBjb25uZWN0aW5nIHBhaXJzIG9mIGRpZmZlcmVudCByb29tcy4gJm5ic3A7Um9vbSAxIGlzIHRoZSBlbnRyYW5jZSB0byB0aGUgY2F2ZS4gVHdvIHJvb21zIGFyZSBuZXZlciBkaXJlY3RseSBjb25uZWN0ZWQgYnkgbW9yZSB0aGFuIG9uZSBjb3JyaWRvci48XC9wPlxyXG5cclxuPHA+QWx3YXlzIHBsYW5uaW5nIGFoZWFkLCBCZXNzaWUgcHJldmlvdXNseSBkZXBvc2l0ZWQgYSBiYWxlIG9mIGhheSBpbiBlYWNoIG9mIEsgKDEgJmx0Oz0gSyAmbHQ7PSAxNCkgZGlmZmVyZW50IHJvb21zIHNvIHNoZSB3aWxsIGhhdmUgZm9vZCBhdmFpbGFibGUgZHVyaW5nIGhlciBleHBlZGl0aW9uLiAmbmJzcDtPZiBjb3Vyc2UganVzdCBsaWtlIHBlb3BsZSwgZXZlcnkgdGltZSBCZXNzaWUgY29uc3VtZXMgYSBiYWxlIG9mIGhheSwgaGVyICZxdW90O2ZhdG5lc3MmcXVvdDsgaW5kZXggaW5jcmVhc2VzIGJ5IG9uZSB1bml0LjxcL3A+XHJcblxyXG48cD5XaGVuIHNoZSBlbnRlcnMgdGhlIGNhdmUsIGhlciBmYXRuZXNzIGluZGV4IGlzIDAgdW5pdHMuIEV2ZXJ5IGNvcnJpZG9yIGluIHRoZSBjYXZlIGhhcyBhIGNlcnRhaW4gd2lkdGg7IEJlc3NpZSBjYW4gb25seSBmaXQgdGhyb3VnaCBhIGNvcnJpZG9yIGlmIGhlciBmYXRuZXNzIGluZGV4IGlzIG5vIGxhcmdlciB0aGFuIHRoYXQgY29ycmlkb3ImIzM5O3Mgd2lkdGguJm5ic3A7PFwvcD5cclxuXHJcbjxwPkJlc3NpZSB3YW50cyB0byBlYXQgYXMgbXVjaCBhcyBwb3NzaWJsZSBkdXJpbmcgaGVyIHRyaXAgaW50byB0aGUgY2F2ZSBidXQgd2FudHMgdG8gbWFrZSBzdXJlIHRoYXQgc2hlIGRvZXMgbm90IGdyb3cgdG9vIGZhdCBhbmQgdHJhcCBoZXJzZWxmIGluIHRoZSBwcm9jZXNzIChhdCB0aGUgZW5kIG9mIGhlciB0cmlwIHNoZSBtdXN0IGV4aXQgdGhlIGNhdmUgYXQgcm9vbSAxKS4gJm5ic3A7SGVscCBoZXIgZGV0ZXJtaW5lIHRoZSBtYXhpbXVtIGFtb3VudCBvZiBoYXkgc2hlIGNhbiBlYXQuJm5ic3A7ICZuYnNwO05vdGUgdGhhdCBCZXNzaWUgY2FuIGRlY2lkZSB0byBwYXNzIHRocm91Z2ggYSByb29tIGNvbnRhaW5pbmcgYSBiYWxlIG9mJm5ic3A7IGhheSB3aXRob3V0IGVhdGluZyB0aGUgaGF5LCBpZiBzaGUgd2lzaGVzLjxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IFRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogTiAsIE0sIGFuZCBLPFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLksrMTogRWFjaCBvZiB0aGVzZSBsaW5lcyBjb250YWlucyB0aGUgaW5kZXggKDEuLk4pIG9mIGEgcm9vbSBjb250YWluaW5nIGEgJm5ic3A7YmFsZSBvZiBoYXkuPFwvbGk+XHJcblx0PGxpPkxpbmVzIEsrMi4uSytNKzE6IEVhY2ggb2YgdGhlc2UgbGluZXMgY29ycmVzcG9uZHMgdG8gYSBiaWRpcmVjdGlvbmFsIGNvcnJpZG9yIGFuZCBjb250YWlucyB0aHJlZSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IGluZGljZXMgb2YgdGhlIHR3byByb29tcyBjb25uZWN0ZWQgYnkgdGhlIGNvcnJpZG9yLCBhbmQgdGhlIGNvcnJpZG9yJiMzOTtzIGludGVnZXIgd2lkdGggKDEuLjEwMCkuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogQSBzaW5nbGUgaW50ZWdlciBnaXZpbmcgdGhlIG1heGltdW0gbnVtYmVyIG9mIGJhbGVzIG9mIGhheSBCZXNzaWUgY2FuIGVhdCAmbmJzcDthbmQgc3RpbGwgc3VjY2Vzc2Z1bGx5IGV4aXQgdGhlIGNhdmUuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiPHA+QWxsIGNvcnJpZG9ycyBsZWF2aW5nIHRoZSBlbnRyYW5jZSByb29tIGhhdmUgd2lkdGggYXQgbW9zdCAzLiAmbmJzcDtUaHVzLCByZXR1cm5pbmcgdG8gdGhhdCByb29tIEJlc3NpZSBtdXN0IGhhdmUgZWF0ZW4gbm8gbW9yZSB0aGFuIDMgYmFsZXMuIENvbWJpbmVkIHdpdGggdGhlIGJhbGUgaW4gdGhhdCByb29tLCA0IGlzIHRoZSBtYXhpbXVtIG51bWJlciBvZiBiYWxlcyB0aGF0IGNhbiBiZSBjb25zdW1lZC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > USA Computing Olympiad > 2003-2004 Season > USACO US Open 2004 Contest > Orange 1번

  • 데이터를 추가한 사람: goooora