题意大概是有10e5个的点，每个点属于一个块，编号相邻的两个块之间的点可以互通。然后还有额外的10e5条边。一开始算了了一下如果暴力做，构图的时间就直接让你TLE。后来想到了把块独立出来，块与块之间连边，费用为c。点与所属块之间连边费用为0。然后用spfa算法去做了。结果还是TLE，后来改用了静态邻接表，还是TLE。然后改用了堆优化的djs算法。成功wa了。后来跑了一组数据发现这样构图会有问题的。本来不能到达的点也可以到达了。 最后看了大牛的解法，发现可以把块拆成两个块。就像高铁站一样，可以分成铁路出发和铁路到达。这样就不会混在一起了。相邻的高铁站可以用，前一个的出发到后一个的到达，后一个的出发到前一个的到达，费用为c。然后每个点连一个出发边到出发，到达边到到达，费用为0。然后跑一边最短路算法。
#include<iostream> #include<cmath> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<queue> using namespace std; const int maxx = 1e5 + 5; const int inf = 0x3f3f3f3f; int to[6 * maxx], cost[6 * maxx], pre[maxx * 6], edge[maxx * 3]; int dis[maxx * 3 + 1000]; bool vis[maxx * 3 + 1000]; int n, m, c; int tot; struct node { int d, from; friend bool operator<(node a, node b) { return a.d > b.d; } }; void addedge(int aa, int bb, int cc) { to[tot] = bb, pre[tot] = edge[aa], cost[tot] = cc, edge[aa] = tot++; } //void spfa() //{ // for (int i = 1; i <= 2 * n; i++) // { // dis[i] = inf; // vis[i] = 0; // } // queue<int >qu; // qu.push(1); // dis[1] = 0; // while (!qu.empty()) // { // int now = qu.front(); qu.pop(); // vis[now] = 0; // for (int i = edge[now]; i != -1; i = pre[i]) // { // int nex = to[i], need = cost[i]; // if (dis[nex] > dis[now] + need) // { // dis[nex] = dis[now] + need; // if (!vis[nex]) // { // qu.push(nex); // vis[nex] = 1; // } // } // } // } //} void djs() { for (int i = 1; i <= 3 * n; i++) { dis[i] = inf; vis[i] = 0; } priority_queue<node>qu; qu.push(node{ 0,1 }); dis[1] = 0; while (!qu.empty()) { node now = qu.top(); qu.pop(); if (now.d > dis[now.from]) continue; //vis[now.from] = 1; for (int i = edge[now.from]; i != -1; i = pre[i]) { int nex = to[i], need = cost[i]; if (dis[now.from] + need < dis[nex]) { qu.push(node{ dis[nex] = dis[now.from] + need ,nex }); } } } } int main() { int t, cnt = 1; scanf("%d", &t); while (t--) { scanf("%d%d%d", &n, &m, &c); tot = 0; for (int i = 1; i <= 3 * n; i++) edge[i] = -1; for (int i = 1; i <= n; i++) { int aa; scanf("%d", &aa); addedge(i, aa * 2 - 1 + n, 0); addedge(aa * 2 + n, i, 0); } for (int i = 1; i < n; i++) { addedge(2 * i + n - 1, 2 * (i + 1) + n, c); addedge(n + 2 * (i + 1) - 1, n + 2 * i, c); } for (int i = 1; i <= m; i++) { int aa, bb, cc; scanf("%d%d%d", &aa, &bb, &cc); addedge(aa, bb, cc); addedge(bb, aa, cc); } djs(); if (dis[n] != inf) printf("Case #%d: %d\n", cnt++, dis[n]); else printf("Case #%d: %d\n", cnt++, -1); } return 0; }本人愚见~~~~
