#include<bits/stdc++.h>
#include<queue>
using namespace std;
#define maxn 300005
#define ll long long
struct qnode{
ll v,c,id;
qnode(){}
qnode(ll v,ll c,ll id):v(v),c(c),id(id){}
bool operator<(
const qnode&r)
const{
return c>
r.c;
}
};
struct Edge{ll to,nxt,w,id;}edge[maxn<<
1];
ll n,m,k,head[maxn],tot,vis[maxn],dist[maxn];
void init(){
tot=
0;
memset(head,-
1,
sizeof head);
}
void addedge(ll u,ll v,ll w,ll id){
edge[tot].to=v;edge[tot].nxt=head[u];edge[tot].id=id;edge[tot].w=w;head[u]=tot++
;
}
priority_queue<qnode>
pq;
vector<ll>
vec;
void dijkstra(ll s){
memset(vis,0,
sizeof vis);
memset(dist,0x3f,
sizeof dist);
dist[s]=
0;
pq.push(qnode(s,0,
0));
while(!
pq.empty()){
qnode tmp=
pq.top();
pq.pop();
ll u=
tmp.v;
if(vis[u])
continue;
vis[u]=
1;
vec.push_back(tmp.id);
if(vec.size()==k+
1)
return;
for(
int i=head[u];i!=-
1;i=
edge[i].nxt){
ll v=edge[i].to,cost=
edge[i].w;
if(vis[v])
continue;
if(dist[v]>dist[u]+
cost){
dist[v]=dist[u]+
cost;
pq.push(qnode(v,dist[v],edge[i].id));
}
}
}
}
int main(){
init();
int u,v,w;
cin>>n>>m>>
k;
for(
int i=
1;i<=m;i++
){
cin>>u>>v>>
w;
addedge(u,v,w,i);
addedge(v,u,w,i);
}
dijkstra(1);
k=min(k,n-
1);
cout<<k<<
endl;
for(
int i=
1;i<=k;i++
)
cout<<vec[i]<<
" ";
return 0;
}
转载于:https://www.cnblogs.com/zsben991126/p/10367525.html
