Edge Deletion CodeForces - 1076D

http://codeforces.com/contest/1076/problem/D

求单源最短路时保存一下路径 最后就是一棵树 然后bfs一遍即可

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int maxn=3e5+10;
const int maxm=3e5+10;
struct node1
{
ll w;
int id,v,next;
};
struct node2
{
ll val;
int id;
bool friend operator < (node2 n1,node2 n2){
return n1.val>n2.val;
}
};
struct node3
{
int id,v;
};
node1 edge[2*maxm];
priority_queue <node2> que;
node3 pre[maxn];
vector <node3> gou[maxn];
queue <int> queque;
ll dis[maxn];
int first[maxn],book[maxn],ans[maxm];
int n,m,k,num;
void addedge(int id,int u,int v,ll w)
{
edge[num].id=id;
edge[num].v=v;
edge[num].w=w;
edge[num].next=first[u];
first[u]=num++;
}
void dijkstra()
{
node2 tmp;
ll w;
int i,id,u,v;
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
tmp.val=0,tmp.id=1;
que.push(tmp);
while(!que.empty()){
tmp=que.top();
que.pop();
u=tmp.id;
if(book[u]) continue;
book[u]=1;
for(i=first[u];i!=-1;i=edge[i].next){
id=edge[i].id,v=edge[i].v,w=edge[i].w;
if(!book[v]&&dis[v]>dis[u]+w){
pre[v].id=id,pre[v].v=u;
dis[v]=dis[u]+w;
tmp.val=dis[v],tmp.id=v;
que.push(tmp);
}
}
}
}
void bfs()
{
int i,id,u,v;
memset(book,0,sizeof(book));
queque.push(1);
book[1]=1;
num=0;
if(num==k) return;
while(!queque.empty()){
u=queque.front();
queque.pop();
for(i=0;i<gou[u].size();i++){
id=gou[u][i].id,v=gou[u][i].v;
if(!book[v]){
queque.push(v);
book[v]=1;
ans[++num]=id;
if(num==k) return;
}
}
}
}
int main()
{
node3 tmp;
ll w;
int i,u,v;
scanf("%d%d%d",&n,&m,&k);
memset(first,-1,sizeof(first));
num=0;
for(i=1;i<=m;i++){
scanf("%d%d%lld",&u,&v,&w);
addedge(i,u,v,w),addedge(i,v,u,w);
}
dijkstra();
for(i=2;i<=n;i++){
tmp.id=pre[i].id,tmp.v=pre[i].v;
gou[i].pb(tmp);
tmp.id=pre[i].id,tmp.v=i;
gou[pre[i].v].pb(tmp);
}
bfs();
printf("%dn",num);
for(i=1;i<=num;i++) printf("%d ",ans[i]);
printf("n");
return 0;
}

最后

以上就是重要项链为你收集整理的Edge Deletion CodeForces - 1076D的全部内容，希望文章能够帮你解决Edge Deletion CodeForces - 1076D所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。