백준
백준 소스코드 [C++] 1865 웜홀
Hani_Levenshtein
2020. 9. 1. 22:07
https://www.acmicpc.net/problem/1865
1865번: 웜홀
첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), �
www.acmicpc.net
백준 소스코드 [C++] 1865 웜홀
#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
typedef long long ll;
using namespace std;
int V, E, W, v, e, weight;
vector <pair<int, int> >adj[500];
void bellman(int src) {
vector <ll> srctodesti(V, 987654321);
srctodesti[src] = 0;
bool check = false;
for (int iter = 0;iter < V;iter++) {
check = false;
for (int here = 0;here < V;here++) {
for (int num = 0;num < (int)adj[here].size();num++) {
int there = adj[here][num].first;
int cost = adj[here][num].second;
if (srctodesti[there] > srctodesti[here] + cost) {
srctodesti[there] = srctodesti[here] + cost;
if (iter == V - 1)check = true;
}
}
}
}
if (check == true) cout << "YES" << '\n';
else cout << "NO" << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--) {
cin >> V >> E >> W;
for (int i = 0;i < V;i++) adj[i].clear();
for (int i = 0;i < E;i++) {
cin >> v >> e >> weight;
adj[v - 1].push_back({ e - 1,weight });
adj[e - 1].push_back({ v - 1,weight });
}
for (int i = 0;i < W;i++) {
cin >> v >> e >> weight;
adj[v - 1].push_back({ e - 1,-weight });
}
bellman(0);
}
return 0;
}