| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1283172 | hagerfarag13 | 통행료 (IOI18_highway) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define ll long long
#define el "\n"
#define pb push_back
#define sz size()
#define fi first
#define se second
using namespace std;
const ll mod = 1e9 + 7;
const ll N = 1000;
const int d1[] = {1, -1, 0, 0};
const int d2[] = {0, 0, 1, -1};
const char d3[] = {'D', 'U', 'R', 'L'};
const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
ll n, m, k, mx = 0, mn = INT_MAX;
bool cyc = 0;
/*
bool valid(int x, int y)
{
if (x < n && x >= 0 && y < m && y >= 0 && (v[x][y] == '.' ))
return 1;
else
return 0;
}
*/
void dfs(ll x,ll y)
{}
void calc(ll i, ll c)
{
// base
// transition
}
/*
const double by=3.14;*/
int main()
{
if (fopen("in.txt", "r"))
{
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
}
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
while(t--){
ll n,m,s,e;
cin>>n>>m>>s>>e;
ll vis[N]={},cost[n+1]={},par[n+1];
for(int i=1;i<=n;i++)cost[i]=1e18;
vector<pair<ll,ll>>adj[n+1];
for(int i=0;i<m;i++){
ll x,y,z;
cin>>x>>y>>z;
adj[x].pb({y,z});
adj[y].pb({x,z});
}
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<>>pq;
pq.push({0,s});
while(pq.sz){
auto [p,u]=pq.top();
pq.pop();
if(vis[u])continue;
vis[u]=1;
for(auto [x,y]:adj[u]){
if(y+p<cost[x]){
par[x]=u;
cost[x]=y+p;
pq.push({p+y,x});
}
}
}
if(cost[e]==1e18){
cout<<"NONE"<<el;
continue;
}
ll ans=0;
ll r=e;
ans+=cost[r];
cout<<ans;
cout<<el;
}
return 0;
}