#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 result; if(Bellman(Graph, result)){ printf("-1"); return 0; } for(int i = 1; i < result.size(); i++){ printf("%lld\n", result[i]); } return 0; } bool Bellman(std::vector& Graph, std::vector& result){ int vertexSize = Graph.size(); std::vector> table(vertexSize + 1, std::vector(vertexSize, INT_MAX)); result.resize(vertexSize, 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++){ long long 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; long long int sum = from + to; if(from == INT_MAX || to == INT_MAX){ sum = INT_MAX; } if(minimum > sum){ minimum = sum; } } table[repet][current] = minimum; } } for(int current = 0; current < vertexSize; current++){ long long 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; long long int sum = from + to; if(from+to > INT_MAX){ sum = INT_MAX; } if(minimum > sum){ minimum = sum; } } if(minimum >= INT_MAX){ result[current] = -1; table[vertexSize][current] = minimum; continue; } if(minimum != table[vertexSize-1][current]){ return true; } result[current] = minimum; table[vertexSize][current] = minimum; } return false; }

제출 #22340

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: