题意：
给出n点m边的无向图，每条边都有权值。
要求最多保留k条边使得最短路径不变的点最多。
思路：
最短路的性质，dijkstra优先队列中的前k kk条边就是答案。
因为要尽可能的保证多一条边就会被答案有贡献，而dijkstra的前k条边松弛条件最多的边，也就是说能够对答案产生贡献最多的一些边。
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=4e5+7,maxm=1e6+7,mod=1e9+7; int n,m,k,st[maxn]; ll dis[maxn]; struct node{ int v,id; ll w; node(int vv,int ii,ll ww){ v=vv;id=ii;w=ww; } bool operator<(const node &a)const{ return w>a.w; } }; vector<node>g[maxn]; vector<int>ans; void bfs(){ memset(dis,0x3f,sizeof dis); dis[1]=0; priority_queue<node>q; q.push({1,0,0}); while(!q.empty()&&ans.size()<=k){ node t=q.top(); q.pop(); int ne=t.v,id=t.id; //cout<<ne<<" "<<st[ne]<<endl; ll d=t.w; if(st[ne]) continue; st[ne]=1; ans.push_back(id); for(int i=0;i<g[ne].size();i++){ int j=g[ne][i].v; //cout<<ne<<" "<<j<<" "<<dis[j]<<" "<<dis[ne]<<" "<<g[ne][i].w<<endl; if(dis[j]>dis[ne]+g[ne][i].w){ // cout<<ne<<" "<<j<<" "<<dis[j]<<" "<<dis[ne]<<" "<<g[ne][i].w<<endl; dis[j]=dis[ne]+g[ne][i].w; q.push({j,g[ne][i].id,dis[j]}); } } } } int main(){ n=read,m=read,k=read; rep(i,1,m){ int u=read,v=read; ll w=read; g[u].push_back({v,i,w}); g[v].push_back({u,i,w}); } bfs(); cout<<ans.size()-1<<"\n"; for(int i=1;i<ans.size();i++) cout<<ans[i]<<" "; return 0; }
