結果

問題 No.17 2つの地点に泊まりたい
コンテスト
ユーザー plasma_e
提出日時 2019-01-17 21:23:44
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,190 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 455 ms
コンパイル使用メモリ 92,948 KB
最終ジャッジ日時 2026-06-07 06:25:40
合計ジャッジ時間 1,271 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:12:26: error: 'int64_t' is not a member of 'std'; did you mean 'int64_t'?
   12 |         std::vector<std::int64_t> cost(N);
      |                          ^~~~~~~
In file included from /usr/include/x86_64-linux-gnu/sys/types.h:155,
                 from /usr/include/stdlib.h:514,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/cstdlib:83,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/ext/string_conversions.h:45,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/basic_string.h:4444,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/string:56,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/locale_classes.h:42,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/ios_base.h:43,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/ios:46,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/ostream.h:43,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/ostream:42,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/iostream:43,
                 from main.cpp:1:
/usr/include/x86_64-linux-gnu/bits/stdint-intn.h:27:19: note: 'int64_t' declared here
   27 | typedef __int64_t int64_t;
      |                   ^~~~~~~
main.cpp:12:33: error: template argument 1 is invalid
   12 |         std::vector<std::int64_t> cost(N);
      |                                 ^
main.cpp:12:33: error: template argument 2 is invalid
main.cpp:13:24: error: 'begin' was not declared in this scope; did you mean 'std::begin'?
   13 |         for (auto& c : cost)
      |                        ^~~~
      |                        std::begin
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc/

ソースコード

diff #
raw source code 

#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<set>
#include<map>

int main()
{
	int N;
	std::cin >> N;
	std::vector<std::int64_t> cost(N);
	for (auto& c : cost)
	{
		std::cin >> c;
	}
	std::vector<std::map<int, std::int64_t>> edge(N);
	int M;
	std::cin >> M;
	for (int i = 0; i < M; ++i)
	{
		int A, B;
		std::int64_t C;
		std::cin >> A >> B >> C;
		edge[A][B] = C;
		edge[B][A] = C;
	}
	std::int64_t ecost[50][50];
	for (int i = 0; i < N; ++i)
	{
		for (int k = 0; k < N; ++k)
		{
			ecost[i][k] = std::numeric_limits<int>::max();
			if (edge[i].count(k))
			{
				ecost[i][k] = edge[i][k];
			}
		}
	}
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			for (int k = 0; k < N; ++k)
			{
				ecost[j][k] = std::min(ecost[j][k], ecost[j][i] + ecost[i][k]);
			}
		}
	}
	std::int64_t min = std::numeric_limits<int>::max();
	for (int i = 1; i < N - 1; ++i)
	{
		for (int k = 1; k < N - 1; ++k)
		{
			if (i == k)
			{
				continue;
			}
			min = std::min(min,
				cost[i] + cost[k] + ecost[0][i] + ecost[i][k] + ecost[k][N - 1]);
		}
	}

	std::cout << min << std::endl;
}
0