[BOJ 28354] 링크 컷 토마토

https://www.acmicpc.net/problem/28354

28354번: 링크 컷 토마토

 

- 문제 요약

 

토마토가 꼭지를 안테나처럼 사용해 연결을 형성하고 끊으며 네트워크를 이룬다는 사실은 잘 알려져 있다.

토마토 간의 연결은 날짜가 바뀌는 순간에만 형성되거나 끊어질 수 있으며, 임의의 두 토마토 사이의 연결 상태는 하루에 두 번 이상 바뀌지 않는다.

토마토 네트워크를 전공한 농부 존은 토마토의 연결 상태와 숙성도의 상관관계를 발견했다.

존의 발견에 따르면, 익은 토마토와 덜 익은 토마토가 하루 간 연결되어 있는다면 덜 익은 토마토는 익은 토마토의 영향을 받아 익게 된다.

끈질긴 연구 끝에 존은 토마토 사이의 연결 상태를 관찰하는 기기를 개발했다.

이 기기를 사용하면 0일에 어떤 토마토가 익어 있고 어떤 토마토들끼리 연결되어 있는지 알 수 있으며, 임의의 두 토마토 사이의 연결이 언제 형성되고 끊어지는지도 추적할 수 있다.

찬우는 천하제일 코딩대회 출제비를 탈탈 털어 존의 기기와 1부터 N까지의 번호가 하나씩 붙은 토마토 N개를 샀지만, 어떤 토마토가 언제 익는지 알아내지 못했다.

찬우가 잘 익은 토마토를 먹을 수 있도록 존의 기기에서 얻은 정보로 각 토마토가 익는 날짜를 계산하는 프로그램을 작성해 주자.

 

 

- 알고리즘 정리

 

다익스트라를 활용해서 풀 수 있습니다.

간선 변화를 통해 각 간선에 대한 lifetime을 계산할 수 있고, 이를 바탕으로 인접한 토마토가 영향을 받는 시간을 구해줄 수 있습니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 200001
int n,m,k,q,arr[MAX],result[MAX];
map<pair<int,int>,int>Map;
vector<tuple<int,int,int>>VV[MAX];

int main(){
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    cin>>n>>m>>k>>q;
    for(int i=1,u,v;i<=m;i++){
    	cin>>u>>v;
		Map[{u,v}]=0;
	}
    for(int i=1;i<=k;i++){
    	cin>>arr[i];
	}
    for(int i=1;i<=q;i++){
        int t,u,v;
        cin>>t>>u>>v;
        auto it=Map.find({u,v});
        if(it==Map.end()){
        	Map.emplace_hint(it,make_pair(u,v),t);
		}
        else{
            int st=it->second,ed=t-1;
            VV[u].emplace_back(v,st,ed);
            VV[v].emplace_back(u,st,ed);
            Map.erase(it);
        }
    }
    for(auto [e,st]:Map){
        auto [u,v]=e;
		int ed=400000;
        VV[u].emplace_back(v,st,ed);
        VV[v].emplace_back(u,st,ed);
    }
    memset(result,0x3f,sizeof(result));
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>>p;
    for(int i=1;i<=k;i++){
    	p.emplace(result[arr[i]]=0,arr[i]);
	}
    while(!p.empty()){
        auto [c,v]=p.top();
        p.pop();
        if(c!=result[v]){
        	continue;
		}
        for(auto [i,s,e]:VV[v]){
        	if(c<=e&&result[i]>max(s,c)+1){
        		p.emplace(result[i]=max(s,c)+1,i);
			}
		}
    }
    for(int i=1;i<=n;i++){
    	cout<<(result[i]<0x3f3f3f3f?result[i]:-1)<<" ";
	}
}

코드 제출 결과