[CF 1076D] Edge Deletion

[CF 1076D] Edge Deletion - 1800

문제 설명 : 

풀이 : 

다익스트라 알고리즘의 원리를 얼마나 잘 알고있는지를 물어보는 문제이다. 다익스트라 알고리즘을 돌면서 매 번 dist[]값이 가장 작은 노드를 찾아가서 그 노드에서 갈 수 있는 edge들을 갱신하는 반복을 작업하게 된다. 이때 중요한 성질은, 다익스트라에서 한 번 방문한 노드는 방문한 순간 dist[]값이 최소라는게 보장된다(여기서 말하는 '방문'이란 min heap의 top에 있는 노드로써 말하는 것이다). 따라서 이 문제에서 최대 k개의 edge를 남겨서 최단경로가 여전히 존재하는 노드의 개수를 최대한 많이 남기라는 것은 다익스트라를 돌리면서 방문하게 되는 k개의 노드를 저장하면 되는 것이다. 그리고 본인이 어떤 edge를 지나왔는지는 이전 과정에서 미리 저장해두면 된다.

주의할 점 : 

-

배울 점 : 

다익스트라 알고리즘을 실행하면서 어느 노드를 방문하는 순간, 그 노드의 dist[]값은 반드시 최소가 된다는 보장을 할 수 있다(추후에 더 작은 값으로 갱신되지 않는다는 것이다). 또한 아래 코드의 69줄에 if(visited[node]) continue; 문장이 있는데, 사실 이 코드는 다익스트라 알고리즘 자체만 돌릴 때는 넣어도 되고 안 넣어도 되는 문제이다. 하지만 이 문제에는 꼭 넣어주어야 하는데, 다익스트라 알고리즘은 같은 노드를 여러번 방문할 수도 있기 때문이다. (물론 dist[]값은 이미 첫 방문 때 결정되었다). 그래서 두번째 방문부터는 같은 edge를 여러번 정답으로 추가될 수 있기 때문에 이 문제에서는 딱 한 번만 방문하도록 제한을 걸었다.

 

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
#include<tuple>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b; S(){}S(int _a,int _b)
    { a=_a; b=_b; }
    const bool operator<(const S &o) const{
        return a<o.a;}
};
string exm;
inline void exf(void){ cout<<exm<<"\n"; exit(0); }
template <typename T>
inline void showAll(vector<T> &v,string sep=""){
    for(T &here:v) cout<<here<<sep;}
template <typename T>
inline vector<int> int_seperation(T N,int d=10){
    vector<int> v; while(N){v.push_back(N%d); N/=d;}
    reverse(v.begin(),v.end()); return v; }
/*********************Contest Template***********************/
const int SIZE= 300009;
 
int V,E,k;
ll dist[SIZE];
int visited[SIZE]={0};
int trace[SIZE]={0};
vector<pair<pll,int>> graph[SIZE];
 
int main(){
    scanf("%d %d %d",&V,&E,&k);
 
    for(int i=0 ; i<E ; i++){
        int a,b,c;  scanf("%d %d %d",&a,&b,&c);
        graph[a].push_back({{c,b},i+1});
        graph[b].push_back({{c,a},i+1});
    }
 
    for(int i=1 ; i<=V ; i++){
        dist[i]=1LL<<61;
    }
 
    dist[1]=0;
 
    priority_queue<pll,vector<pll>,greater<pll>> mpq;
    mpq.push({0,1});
    visited[1]=true;
    vector<int> ans;
 
    while(!mpq.empty()){
        ll node=mpq.top().second,cost=mpq.top().first; mpq.pop();
        if(visited[node]) continue;
        
        if(trace[node]) ans.push_back(trace[node]);
        if(ans.size()==k) break;
 
        for(auto &here:graph[node]){
            ll next=here.first.second,nextCost=cost+here.first.first;
            int idx=here.second;
 
            if(dist[next]>nextCost && !visited[next]){
                mpq.push({nextCost,next});
                dist[next]=nextCost;
                trace[next]=idx;
            }
        }
        visited[node]=true;
    }
 
    printf("%d\n",ans.size());
    showAll(ans," ");
 
    return 0;
}
/*

*/