[PS]BOJ 11657タイムマシン
##BOJ-11657タイムマシン
https://www.acmicpc.net/problem/11657
この問題は、時間
Cが負の数を生じる可能性があるため、ベルマン・フォードアルゴリズムを使用する必要がある.負のフィードバックが存在する場合、出力は
-1万回である.1からA[i]までのすべての距離を出力し、A[i]が1の議定点および他の素子にある場合.
無限の価値がある.このとき-1の答えを印刷することもできます
solution #include<iostream>
#include<vector>
#include<list>
#include<algorithm>
#define MAXN 100000
using namespace std;
int N, M;
vector<list<pair<int, int> > > G; //to, weight
void bellman_ford(int pos) {
vector<int> d(N);
bool b;
fill(d.begin(), d.end(), MAXN);
d[pos] = 0;
for (int i = 0; i < N; i++){
b = false;
for (int j = 0; j < G.size();j++){
for (auto jt = G[j].begin(); jt != G[j].end(); jt++){
if (d[j] != MAXN && d[jt->first]>d[j] + jt->second){
d[jt->first]=d[j] + jt->second;
b = true;
}
}
}
}
if (b){
cout << -1 << endl;
}
else{
for (auto it = d.begin() + 1; it != d.end(); it++){
if (*it == MAXN)
cout << -1 << endl;
else
cout << *it << endl;
}
}
}
int main() {
cin >> N >> M;
G.assign(N, list<pair<int, int> >());
for (int i = 0; i < M; i++){
int from;
pair<int, int> p;
cin >> from >> p.first >> p.second;
p.first--;
G[from - 1].push_back(p);
}
bellman_ford(0);
return 0;
}Copyright (C) 2016 (KimBom) all rights reserved.Reference
この問題について([PS]BOJ 11657タイムマシン), 我々は、より多くの情報をここで見つけました https://velog.io/@springkim/PS-BOJ-11657-타임머신テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol