假定有n个城堡，编号为1至n，有的城堡之间有道路直接相连，有的城堡之间没有道路直接相连。马里奥现在准备从一个城堡出发前往另一个城堡，它有一个魔法棒，可以瞬时通过一条道路，即以0时间通过这条道路，但魔法棒最多只能用一次。马里奥想以最短的时间到达目的地，请编写程序为马里奥选定一条路线以及在什么地方使用魔法棒。假定所有道路为双向，保证从起点肯定能到达目的地。
输入格式:
输入第一行为4个整数n、s、t、m，分别表示城堡数（编号为1至n，n不超过10000），马里奥所在的起点s和想去的终点t，城堡间的道路数目。接下来m行，每行为3个正整数a、b、c，表示城堡a和城堡b之间有一条道路直接相连，通过该道路需要c分钟。
输出格式:
输出为空格间隔的2个整数，第1个整数为马里奥从起点到目的地所需的最短时间；第2个整数表示使用魔法棒的地点，即城堡编号，若有多个可能的地点，则输出编号最小者。
输入样例:
4 1 4 4
1 2 9
2 4 1
1 3 3
3 4 5
输出样例:
1 1
被最后两个测试点的数据范围卡了半天，闹心。非独立完成，有请教他人
AC代码1：求一次s的最短路和t的最短路，然后枚举边，如果这条边的两个端点分别能到s和t，说明有一条路经过这条边能从s到t，那么这条路的最小值就是s到这条边一个端点的最短路+t到另一个端点的最短路。这个邻接表和初始化有必要记一记，因为我很少这么写，只是见过
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;typedef struct {int u, v; //每条边的起点和终点
} Edge;typedef long long ll;
const ll inf = 1e12;
const int N = 1e4 + 10, M = 1e8 + 10;//分别为顶点数和边数
bool vis[N] = {false};
ll diss[N], dist[N]; //diss表示起点s到其他各点的距离，dist表示终点t到其他各点的距离//h表示从某顶点出发的第一条边的编号，e为该条边的终点编号，//w为该条边的权值，ne存储从该顶出发的下一条边的编号，idx为第几条边
int h[N], e[M], w[M], ne[M], idx;
int n, m, s, t; //顶点数 边数 起点 终点
Edge edge[M]; //存储每一条边的信息void add(int a, int b, int c) { //邻接表（头插法）存储边信息e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}void spfa(ll dis[], int u) { //最短路算法spfafor (int i = 1; i <= n; i++) {dis[i] = inf;vis[i] = false;}queue<int> qe;qe.push(u);dis[u] = 0;vis[u] = true;while (!qe.empty()) {int x = qe.front();qe.pop();vis[x] = false;for (int i = h[x]; i != -1; i = ne[i]) {int j = e[i];if (dis[j] > dis[x] + w[i]) {dis[j] = dis[x] + w[i];if (!vis[j]) {qe.push(j);vis[j] = 1;}}}}
}int main() {scanf("%d %d %d %d", &n, &s, &t, &m);memset(h, -1, sizeof(h)); //初始时，每个顶点的第一条边的编号都设为-1，表示没有边for (int i = 0; i < m; i++) { //输入每条边的信息int a, b, c;scanf("%d %d %d", &a, &b, &c);add(a, b, c), add(b, a, c); //双向存储边信息edge[2 * i].u = a, edge[2 * i].v = b;//正向存储每条边的起点和终点edge[2 * i + 1].u = b, edge[2 * i + 1].v = a;//反向存储每条边的起点和终点}spfa(diss, s);//从起点s出发的单源最短路spfa(dist, t);//从终点t出发的单源最短路ll minx = inf;int pos;for (int i = 0; i < 2 * m; i++) {int a = edge[i].u, b = edge[i].v;if (diss[a] + dist[b] < minx) { //寻找最小值minx = diss[a] + dist[b];pos = a;} else if (diss[a] + dist[b] == minx && a < pos) { //最小值相同时，寻找最小编号pos = a;}}printf("%lld %d", minx, pos);return 0;
}
代码1C语言版本
#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef struct {int u, v; //每条边的起点和终点
} Edge;typedef long long ll;
const ll inf = 1e12;
//M的大小不能为1e8及以上，我的不行，提示内存超限！！！！
const int N = 1e4 + 10, M = 1e7 + 1000; //分别为顶点数和边数
int q[N];
int vis[N] = {0};
ll diss[N],dist[N]; // diss表示起点s到其他各点的距离，dist表示终点t到其他各点的距离// h表示从某顶点出发的第一条边的编号，e为该条边的终点编号，// w为该条边的权值，ne存储从该顶出发的下一条边的编号，idx为第几条边
int h[N], e[M], w[M], ne[M], idx;
int n, m, s, t; //顶点数 边数 起点 终点
Edge edge[M]; //存储每一条边的信息void add(int a, int b, int c) { //邻接表（头插法）存储边信息e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}void spfa(ll dis[], int u) { //最短路算法spfafor (int i = 1; i <= n; i++) {dis[i] = inf;vis[i] = 0;}int head = 0, rear = 0;q[rear++] = u;dis[u] = 0;vis[u] = 1;while (head != rear) {int x = q[head++];vis[x] = 0;for (int i = h[x]; i != -1; i = ne[i]) {int j = e[i];if (dis[j] > dis[x] + w[i]) {dis[j] = dis[x] + w[i];if (!vis[j]) {q[rear++] = j;vis[j] = 1;}}}}
}int main() {scanf("%d %d %d %d", &n, &s, &t, &m);memset(h, -1,sizeof(h)); //初始时，每个顶点的第一条边的编号都设为-1，表示没有边for (int i = 0; i < m; i++) { //输入每条边的信息int a, b, c;scanf("%d %d %d", &a, &b, &c);add(a, b, c), add(b, a, c); //双向存储边信息edge[2 * i].u = a, edge[2 * i].v = b; //正向存储每条边的起点和终点edge[2 * i + 1].u = b, edge[2 * i + 1].v = a; //反向存储每条边的起点和终点}spfa(diss, s); //从起点s出发的单源最短路spfa(dist, t); //从终点t出发的单源最短路ll minx = inf;int pos;for (int i = 0; i < 2 * m; i++) {int a = edge[i].u, b = edge[i].v;if (diss[a] + dist[b] < minx) { //寻找最小值minx = diss[a] + dist[b];pos = a;} else if (diss[a] + dist[b] == minx && a < pos) { //最小值相同时，寻找最小编号pos = a;}}printf("%lld %d", minx, pos);return 0;
}
AC代码2：分层图，emmm，现在还很懵逼，建完后，总共两个图，使用一次最短路算法，不是我写的代码。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int path[N], h[N], e[N], w[N], ne[N], idx, d[N], q[N], n;
bool st[N];
void add(int a, int b, int c) {e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void spfa(int s) {memset(d, 0x3f, sizeof d);int hh = 0, tt = 0;q[tt++] = s;d[s] = 0;st[s] = 1;while (hh != tt) {int t = q[hh++];st[t] = 0;for (int i = h[t]; ~i; i = ne[i]) {int j = e[i];if (d[j] > d[t] + w[i]) {d[j] = d[t] + w[i];path[j] = t;if (!st[j]) {q[tt++] = j;st[j] = 1;}} else if (n <= 10 && d[j] == d[t] + w[i] && path[j] > t)path[j] = t;}}
}
int main() {memset(h, -1, sizeof h);int s, t, m;scanf("%d%d%d%d", &n, &s, &t, &m);while (m--) {int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c), add(b, a, c), add(a, b + n, 0), add(b, a + n, 0),add(a + n, b + n, c), add(b + n, a + n, c);}spfa(s);int x = t + n;while (x > n)x = path[x];printf("%d %d", d[t + n], x);return 0;
}
