51nod2884

水题 阿 就是先求出 最短路树 然后 从树的底端开始删点就好了

#include<iostream>
#include<queue>
#include<utility>
#include<cstring>
#include<algorithm>
#include<vector>
#define x first
#define y second

using namespace std;

const int N = 3e5 + 10,M = 2e6 + 10;

typedef long long ll;
typedef pair<ll,int> PII;

vector<vector<int> > v(N);

int head[N],to[M],last[M],w[M],cnt = 1;
void add(int a,int b,int c){
    
    to[++cnt] = b;
    w[cnt] = c;
    last[cnt] = head[a];
    head[a] = cnt;
}

int flag[N];ll dist[N],pre[N];
void dij(){
    
    memset(dist,0x3f,sizeof dist);
    priority_queue<PII,vector<PII>,greater<PII> >q;
    q.push({
    0,1});
    dist[1] = 0;
    while(q.size()){
    
        PII p = q.top();
        q.pop();
        if(flag[p.y]) continue;
        flag[p.y] = 1;
        for(int i = head[p.y]; i != -1; i = last[i]){
    
            int j = to[i];
            if(dist[j] > dist[p.y] + w[i]){
    
                dist[j] = dist[p.y] + w[i];
                pre[j] = i;
                q.push({
    dist[j],j});
            }
        }
    }
}

int dep[N];
void dfs(int x,int lastt){
    
    dep[x] = dep[lastt] + 1;
    for(auto j : v[x]){
    
        if(j == lastt) continue;
        dfs(j,x);
    }
}

int main(){
    
    int n,m,k;
    cin >> n >> m >> k;
    memset(head,-1,sizeof head);
    for(int i = 1; i <= m; i++){
    
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        add(x,y,w);
        add(y,x,w);
    }

    dij();

    for(int i = 2; i <= n; i++){
    
        v[to[pre[i] ^ 1]].push_back(i);
    }

    dfs(1,0);

    priority_queue<PII,vector<PII>,less<PII> > q;
    for(int i = 2; i <= n; i++){
    
        if(pre[i] != 0)
        q.push({
    dep[i],pre[i] / 2});
    }

    while(q.size() > k){
    
        q.pop();
    }

    cout << min((int)q.size(),k) << endl;
    while(q.size()){
    
        printf("%d ",q.top().y);
        q.pop();
    }


    return 0;
}