思路

从每个点出发跑 Dijkstra，但是添加了优化，只跑距离前 $k$ 的点（因为是正权所以直接 break）。这样的话理论时间复杂度应该是 $O(n\cdot k\log k)$，2.5 秒应该能卡过，求卡常或者指出算法存在的问题，谢谢。

代码

submission

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <unordered_map>
using namespace std;

int n, m, k;
long long dis[200010];
int vis[200010];
unordered_map<int, unordered_map<int, int> > mp;
map<long long, int> ans;

struct edge
{
    int y, w;
} ;

vector<edge> g[200010];

struct node
{
    int x;
    long long d;

    bool operator < (const node & b) const
    {
        return d > b.d;
    }
} ;

void dijkstra(int s)
{
    priority_queue<node> qq;
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    qq.push((node){s, 0});
    dis[s] = 0;
    while (qq.size())
    {
        int x = qq.top().x;
        qq.pop();
        if (vis[x]) continue;
        vis[x] = 1;
        int ii = min(s, x);
        int jj = max(s, x);
        int p = 0;
        for (map<long long, int>::iterator it = ans.begin(); it != ans.end(); it++)
        {
            if ((*it).first < dis[x])
                p += (*it).second;
            else break;
        }
        if (p >= k) break;
        if (dis[x])
        {
            if (!mp.count(ii) || !mp[ii].count(jj))
                mp[ii][jj] = 1;
            else if (ii != s)
                ans[dis[x]]--;
            ans[dis[x]]++;
        }
        for (int i = 0; i < g[x].size(); i++)
        {
            int y = g[x][i].y;
            int w = g[x][i].w;
            if (dis[y] > dis[x] + w)
            {
                dis[y] = dis[x] + w;
                qq.push((node){y, dis[y]});
            }
        }
    }
}

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++)
    {
        int x, y, w;
        cin >> x >> y >> w;
        g[x].push_back((edge){y, w});
        g[y].push_back((edge){x, w});
    }
    for (int i = 1; i <= n; i++)
        dijkstra(i); 
    long long anss = 0;
    map<long long, int>::iterator i = ans.begin();
    while (k > 0)
    {
        anss = (*i).first;
        k -= (*i).second;
        // cout << anss << endl;
        i++;
    }
    cout << anss << endl;
    return 0;
}