[伯俊]1956号うんどう

2268 ワード
白駿 ps フロイド・ワシェル テキストリンク
[伯俊]1956号うんどう
1.質問
Vの村とEの道路からなる都市があります.道は村と村の間にあり、一方通行です.村のコンビニ1番からV番まで番号があります.
道路に沿ってトレーニングの道を見つけたいです.運動後はスタート地点に戻ったほうがいいので、周期を見つけたいです.しかし、あなたは運動が嫌いなので、道の長さの和を最小にしたいと思っています.
道路情報を取得する場合は、道路の長さの和の最小周期を検索するプログラムを作成します.2つの村を往復する場合も自転車に含めて注意が必要です.
2.入力
最初の行では、VとEはスペースを隔てています.(2≦V≦400,0≦E≦V(V−1)),次のE行はそれぞれ3つの整数a,b,cを与える.これは、a番村からb番村までの距離がcの道路があることを意味します.(注意a→b)距離は10000以下の自然数です.(a,b)同じ道を何度も交わらない.
3.出力
1行目に最小サイクル道路長の和を出力します.モーションパスが見つからない場合は、-1を出力します.
4.解答
  • プルード・ワッシャーを使用しました.
  • サイクルを探す必要があるため、所望の結果値はi==jである.
  • の一般的なプルード・ワッシャーはi==jの位置を0に初期化したが、周期を探す必要があるため、i==jも同様にINFに初期化した.
  • フロイド・ワッシャーが完了すると、i==jポイントで最高値が出力されます.(ただし、すべての値がINFであればループはないので、-1をminValueに代入して出力する.)
    • 5.最初のコードと異なる点
  • サイクルが見つからない場合は、出力-1のコードを削除して変更します.
    • 6.コード
    #include <iostream>
#include <algorithm>
#define INF 1e9

using namespace std;

int graph[401][401];

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	int number_of_villages, number_of_roads;
	cin >> number_of_villages >> number_of_roads;
	
	for (int i = 1; i <= number_of_villages; i++){
		for (int j = 1; j <= number_of_villages; j++) {
			graph[i][j] = INF;
		}
	}
	
	for (int i = 0; i < number_of_roads; i++){
		int from, to, cost;
		cin >> from >> to >> cost;
		graph[from][to] = cost;
	}

	for (int k = 1; k < number_of_villages; k++){
		for (int i = 1; i <= number_of_villages; i++) {
			for (int j = 1; j <= number_of_villages; j++) {
				graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
			}
		}
	}

	int minValue = INF;
	for (int i = 1; i <= number_of_villages; i++){
		minValue = min(minValue, graph[i][i]);
	}
	if (minValue == INF) minValue = -1;
	cout << minValue;
}
    [Ava]toString()の使用
    ASP.NET Core project.json importsってどういう意味ですか?