#include #include #include struct VertexType{ std::vector> To; std::vector> From; }; bool Bellman(std::vector&, std::vector>&); int main(int argc, char* argv[]){ int vertexCount, edgeCount; scanf("%d %d", &vertexCount, &edgeCount); std::vector Graph(vertexCount); for(int i = 0; i < edgeCount; i++){ int from, to, w; scanf("%d %d %d", &from, &to, &w); from--; to--; Graph[from].To.push_back({to, w}); Graph[to].From.push_back({from, w}); } std::vector> table; if(Bellman(Graph, table)){ printf("-1"); return 0; } for(int i = 1; i < table[Graph.size()].size(); i++){ printf("%d\n", table[Graph.size()][i]); } return 0; } bool Bellman(std::vector& Graph, std::vector>& table){ int vertexSize = Graph.size(); table.resize(vertexSize + 1, std::vector(Graph.size(), INT_MAX)); table[0][0] = 0; for(std::pair p : Graph[0].To){ table[0][p.first] = p.second; } for(int repet = 1; repet < vertexSize; repet++){ for(int current = 0; current < vertexSize; current++){ int minimum = table[repet-1][current]; for(std::pair element : Graph[current].From){ long long int from = table[repet - (current > element.first)][element.first]; long long int to = element.second; int sum = from + to; if(from+to > INT_MAX){ sum = INT_MAX; } if(minimum > sum){ minimum = sum; } } table[repet][current] = minimum; } } /*for(std::vector vec : table){ for(int i : vec){ printf("%d ", i); } printf("\n"); }*/ for(int current = 0; current < vertexSize; current++){ int minimum = table[vertexSize-1][current]; for(std::pair element : Graph[current].From){ long long int from = table[vertexSize - (current > element.first)][element.first]; long long int to = element.second; int sum = from + to; if(from+to > INT_MAX){ sum = INT_MAX; } if(minimum > sum){ minimum = sum; } } if(minimum != table[vertexSize-1][current]){ return true; } if(minimum >= INT_MAX){ table[vertexSize][current] = -1; continue; } table[vertexSize][current] = minimum; } return false; }

제출 #22273

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: