如果你并没有想到建反图，而是跑了n遍 dijkstra，那么你就获得了 TLE 70 pts 的好成绩。

不过注意的是在跑除了1号节点的dij时，我们实际上只是关心的是 $n \to 1$ 的最短路，所以我们只许在跑到 $1$ 结点时直接 return 即可。

如下方 TLE 代码：

void dij(int x) {
    while (!q.empty()) q.pop();
    q.push(node{x,0});
    while (!q.empty()) {
        node t = q.top();
        q.pop();
        vis[x][t.p] = true;
        for (int i = head[t.p];i;i = e[i].nxt) {
            if (vis[x][e[i].to]) continue;
            if (dis[x][e[i].to] > dis[x][t.p] + e[i].w) {
                dis[x][e[i].to] = dis[x][t.p] + e[i].w;
                q.push(node{e[i].to,dis[x][e[i].to]});
            }
        }
    }
}

只需要加上一句

if (t.p == 1 && x != 1) return;

即可，注意此时优先队列还不为空，下一次跑记得清空。

此外，你还需要找一个人比较少的时候卡一下评测机波动，然后你就可以卡过去了（本人最后一个点 990ms 卡过，无任何读入优化），保险一点你还可以关掉同步流或直接上快读快写（）