Codeforces - D. Edge Deletion
20003 단어 Codeforces도론최단로
You have to erase some edges of the graph so that at most k edges remain. Let’s call a vertex i good if there still exists a path from 1 to i with length di after erasing the edges.
Your goal is to erase the edges in such a way that the number of good vertices is maximized.
Input The first line contains three integers n, m and k (2≤n≤3⋅105, 1≤m≤3⋅105, n−1≤m, 0≤k≤m) — the number of vertices and edges in the graph, and the maximum number of edges that can be retained in the graph, respectively.
Then m lines follow, each containing three integers x, y, w (1≤x,y≤n, x≠y, 1≤w≤109), denoting an edge connecting vertices x and y and having weight w.
The given graph is connected (any vertex can be reached from any other vertex) and simple (there are no self-loops, and for each unordered pair of vertices there exists at most one edge connecting these vertices).
Output In the first line print e — the number of edges that should remain in the graph (0≤e≤k).
In the second line print e distinct integers from 1 to m — the indices of edges that should remain in the graph. Edges are numbered in the same order they are given in the input. The number of good vertices should be as large as possible.
Examples inputCopy 3 3 2 1 2 1 3 2 1 1 3 3 outputCopy 2 1 2 inputCopy 4 5 2 4 1 8 2 4 1 2 1 3 3 4 9 3 1 5 outputCopy 2 3 2
뚜렷한 방법은 가장 짧은 길의 가장자리, 즉 가장 짧은 길의 나무를 찾아야 한다는 것이다.
그 다음은 시작점부터 시작하는 k개의 경로입니다.
AC 코드:
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include
#define int long long
using namespace std;
const int N=3e5+10;
int n,m,k,pre[N],d[N],vis[N];
int head[N],nex[N<<1],to[N<<1],w[N<<1],id[N<<1],tot;
vector<int> res;
inline void ade(int a,int b,int c,int d){
to[++tot]=b; nex[tot]=head[a]; w[tot]=c; id[tot]=d; head[a]=tot;
}
inline void add(int a,int b,int c,int d){ade(a,b,c,d); ade(b,a,c,d);}
void Dijkstra(){
priority_queue<pair<int,int> > q; memset(d,0x3f,sizeof d); d[1]=0; q.push({0,1});
while(q.size()){
int u=q.top().second; q.pop();
if(vis[u]) continue; vis[u]=1;
for(int i=head[u];i;i=nex[i]){
if(d[to[i]]>d[u]+w[i]){
d[to[i]]=d[u]+w[i]; q.push({-d[to[i]],to[i]});
pre[to[i]]=u;
}
}
}
}
void bfs(){
queue<int> q; q.push(1); memset(vis,0,sizeof vis); vis[1]=1;
while(q.size()){
int u=q.front(); q.pop();
for(int i=head[u];i;i=nex[i]){
if(pre[to[i]]==u&&res.size()<k&&!vis[to[i]]){
res.push_back(id[i]); q.push(to[i]); vis[to[i]]=1;
}
}
}
}
signed main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin>>n>>m>>k;
for(int i=1,a,b,c;i<=m;i++) cin>>a>>b>>c,add(a,b,c,i);
Dijkstra(); bfs();
cout<<res.size()<<'
';
for(int i=0;i<res.size();i++) cout<<res[i]<<' ';
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces 1287C Garland제목 링크:Codeforces 1287C Garland 사고방식: 우리기dp[i][j][0]와 dp[i][j][1]는 각각 i개가 홀수/짝수이고 앞의 i개 안에 j개의 짝수가 있는 상황에서 i개의 최소 복잡도.첫 번...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.