카테고리 없음
BOJ 2307 - 도로검문 (G1)
satturn80
2023. 7. 1. 17:38
어디서 들어본 것 같은 추천문제여서 풀어봤다
풀이)다익스트라
모든 간선을 다 지우면서 확인하는 방법은 O(M*(N+M)logN)이라 힘들어보인다.
여기서 중요한 것은 M개를 다 지워볼 필요가 없다는 것이다.
왜냐? 하나를 지웠는데, 최단경로상의 간선이 아니면 그냥 최단경로를 따라가면 되기 때문이다.
따라서 하나의 최단경로 상의 간선을 지워야 함을 알 수 있다.
그렇다면 여기서 궁금증이 하나 들어야 한다.
여러개의 최단경로가 있을 수 있는데, 하나의 최단경로만 지워도 되는가?
된다.
그 이유는 아주 간단한데, 하나의 최단경로 상의 간선을 지우지 않으면 그 최단경로로 가면 되기 때문이다. 따라서 최적해는 임의의 최단경로상의 간선 위에 있을 수 밖에 없다. (아니라면 무조건 0이 답이라서 상관 x)
따라서 하나의 최단경로에서 모든 간선을 지워보면 남은 최단경로가 알아서 끊겨 최적해를 찾을 수 있다.
#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
using namespace std;
typedef long long ll;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define inf 1e18
typedef pair<ll,ll> P;
ll n, m;
ll dist[1010];
ll prv[1010];
vector<P> adj[1010];
tuple<ll,ll,ll> edge[1010];
vector<tuple<ll,ll,ll>> v;
bool f;
ll ori = 0;
ll ans = 0;
void dijkstra(){
priority_queue<P, vector<P>, greater<P>> pq;
fill(dist+1, dist+n+1, inf);
dist[1]=0;
pq.push({0,1});
while(pq.size()){
auto [w, cur] = pq.top();
pq.pop();
for(auto [next, weight] : adj[cur]){
if(dist[next] > w + weight){
if(f){
prv[next] = cur;
edge[next] = {cur,next,weight};
}
dist[next] = w+weight;
pq.push({dist[next], next});
}
}
}
if(f){
for(int i = n ; i != 1 ; i = prv[i]){
v.push_back(edge[i]);
}
ori = dist[n];
}
else{
if(dist[n]==inf){
cout<<-1;
exit(0);
}
ans = max(ans, dist[n]-ori);
}
}
int main(){
fast;
cin>>n>>m;
for(int i = 0 ; i < m ; i++){
ll a,b,c; cin>>a>>b>>c;
adj[a].push_back({b,c});
adj[b].push_back({a,c});
}
f=1;
dijkstra();
f=0;
for(auto [u,v,w] : v){
adj[u].erase(find(all(adj[u]), pair(v,w)));
adj[v].erase(find(all(adj[v]), pair(u,w)));
dijkstra();
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
cout<<ans;
}