1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <map>
#include <queue>
using namespace std;
struct node{
    int at,cost,k;
};
int sP[10004];
map<int,int> m[10004];
int main(){
    int N,M,K,T;
    scanf(" %d%d%d%d",&N,&M,&K,&T);
    for(int i=0,u,v,w;i<M;++i){
        scanf(" %d%d%d",&u,&v,&w);
        if( m[u][v]==0 || m[u][v] > w )
            m[u][v] = w;
        m[v][u] = m[u][v];
    }
    queue<node> myQ;
    myQ.push( (node){ 1 , 0 , 0 } );
    while( !myQ.empty() ){
        node now = myQ.front();
        myQ.pop();
        if( sP[now.at] && sP[now.at] < now.cost )
            continue;
        sP[now.at] = now.cost;
        if( now.k == K )
            continue;
        for(map<int,int>::iterator it=m[now.at].begin() ; it!=m[now.at].end() ; ++it){
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX