C++ Code

#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

const int N=15*10000+5,inf=0x3f3f3f3f;

struct node{
    int to,w;

    bool operator <(const node x)const
    {
        if(w==x.w) return to>x.to;
        else return w>x.w;
    }
};

int dis[N];
bool st[N];

int n,m;

priority_queue<node> q;
vector<node> g[N];

void dijkstra(int s){
    for(register int i=1;i<=n;i++)
        dis[i]=inf,st[i]=false;

    dis[s]=0;

    q.push((node){s,0});
    while(!q.empty()){
        node e=q.top(),tmp;
        q.pop();
        st[e.to]=true;
        for(register int i=0;i<g[e.to].size();i++){
            tmp=g[e.to][i];
            if(st[tmp.to])
                continue;
            if(dis[tmp.to]>dis[e.to]+tmp.w){
                dis[tmp.to]=dis[e.to]+tmp.w;
                q.push((node){tmp.to,dis[tmp.to]});
            }
        }
    }
}

inline int read()
{
    register int x=0,f=1;
    register char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}

int main()
{
    n=read(),m=read();

    while(m--){
        int y=read(),t=read(),z=read();
        g[y].push_back((node){t,z});
    }

    dijkstra(1);

    if(dis[n]>=inf)
        printf("-1");
    else printf("%d",dis[n]);

    return 0;
}

超时数据

50000 54997
1 2 10000
1 3 2
1 4 3
1 5 4
1 6 5
1 7 6
1 8 7
1 9 8
1 10 9
1 11 10
1 12 11
1 13 12
1 14 13
1 15 14
1 16 15
1 17 16
1 18 17
1 19 18
1 20 19
1 21 20
1 22 21
1 23 22
1 24 23
1 25 24
1 26 25
1 27 26
1 28 27
1 29 28
1 30 29
1 31 30
1 32 31
1 33 32
1 34 33
1 35 34
1 36 35
1 37 36
1 38 37
1 39 38
1 40 39
1 41 40
1 42 41
1 43 42
1 44 43
1 45 44
1 46 45
1 47 46
1 48 47
1 49 48
1 50 49
1 51 50
1 52 51
1 53 52
1 54 53
1 55 54
1 56 55
1 57 56
1 58 57
1 59 58
1 60 59
1 61 60
1 62 61
1 63 62
1 64 63
1 65 64
1 66 65
1 67 66
1 68 67
1 69 68
1 70 69
1 71 70
1 72 71
1 73 72
1 74 73
1 75 74
1 76 75
1 77 76
1 78 77
1 79 78
1 80 79
1 81 80
1 82 81
1 83 82
1 84 83
1 85 84
1 86 85
1 87 86
1 88 87
1 89 88
1 90 89
1 91 90
1 92 91
1 93 92
1 94 93
1 95 94
1 96 95
1 97 96
1 98 97
1 99 98
1 100 99
1 101 100
1 102 101
1 103 102
1 104 103
1 105 104
1 106 105
1 107 106
1 108 107
1 109 108
1 110 109
1 111 110
1 112 111
1 113 112
1 114 113
1 115 114
1 116 115
1 117 116
1 118 117
1 119 118
1 120 119
1 121 120
1 122 121
1 123 122
1 124 123
1 125 124
1 126 125
1 127 126
1 128 127
1 129 128
1 130 129
1 131 130
1 132 131
1 133 132
1 134 133
1 135 134
1 136 135
1 137 136
1 138 137
1 139 138
1 140 139
1 141 140
1 142 141
1 143 142
1 144 143
1 145 144
1 146 145
1 147 146
1 148 147
1 149 148
1 150 149
1 151 150
1 152 151
1 153 152
1 154 153
1 155 154
1 156 155
1 157 156
1 158 157
1 159 158
1 160 159
1 161 160
1 162 161
1 163 162
1 164 163
1 165 164
1 166 165
1 167 166
1 168 167
1 169 168
1 170 169
1 171 170
1 172 171
1 173 172
1 174 173
1 175 174
1 176 175
1 177 176
1 178 177
1 179 178
1 180 179
1 181 180
1 182 181
1 183 182
1 184 183
1 185 184
1 186 185
1 187 186
1 188 187
1 189 188
1 190 189
1 191 190
1 192 191
1 193 192
1 194 193
1 195 194
1 196 195
1 197 196
1 198 197
1 199 198
1 200 199
1 201 200
1 202 201
1 203 202
1 204 203
1 205 204
1 206 205
1 207 206
1 208 207
1 209 208
1 210 209
1 211 210
1 212 211
1 213 212
1 214 213
1 215 214
1 216 215
1 217 216
1 218 217
1 219 218
1 220 219
1 221...

标准答案：5102