通常情况下找到N个节点、M 条边的无向图中某两点的最短路径很简单。假设每条边都有各自的长度以及删除这条边的代价，那么给出两个点X和Y，删除一些边可以使得X到Y的最短路径增加，求删除边最少的代价。
第一行包含参数N和M，分别表示节点和边的个数（2 ≤N≤ 1000，1 ≤M≤ 11000 ）； 第二行包含参数X和Y，表示源点和终点（ 1 ≤ X，Y ≤ N，X ≠ Y）； 剩下M行每行包含4个参数Ui、Vi、Wi和Ci，分别表示节点Ui和Vi之间边的长度Wi以及删除的代价Ci （ 1 ≤ Ui , Vi ≤ N， 0 ≤Wi, Ci ≤1000 ）; 如果某行N=M=0就表示输入结束。
2 3 1 2 1 2 2 3 1 2 2 4 1 2 3 5 4 5 1 4 1 2 1 1 2 3 1 1 3 4 1 1 1 4 3 2 2 2 2 3 4 5 2 3 1 2 3 2 2 4 3 4 1 3 2 3 3 4 2 3 1 4 0 1 0 0
7 3 6
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
#include <queue>
using namespace std;
const int INF = 0x3fffffff;
const int maxn = 1010;
int d[maxn][maxn]; // distance .
int cost[maxn][maxn]; // cost.
bool vis[maxn][maxn]; // mark;
int n, m;
int s, t; // start, end point.
int w, h; // mark the edges.
queue<int> que;
bool inque[maxn];
int p[maxn]; // parent.
int dis[maxn];
void spfa() {
while(!que.empty()) que.pop();
memset(inque, false, sizeof(inque));
for(int i = 1; i <= n; i++) dis[i] = INF;
dis[s] = 0;
inque[s] = true;
que.push(s);
while(!que.empty()) {
int u = que.front(); que.pop();
for(int i = 1; i <= n; i++) {
if(vis[u][i]) {
if(dis[i] > dis[u]+d[u][i]) {
dis[i] = dis[u]+d[u][i];
p[i] = u;
if(!inque[i]) {
que.push(i);
inque[i] = true;
}
}
}
}
inque[u] = false;
}
}
int work() {
int ans = INF;
int tmp = t; // end point.
while(p[tmp] != s) {
ans = min(ans, cost[tmp][p[tmp]]);
tmp = p[tmp];
}
ans = min(ans, cost[s][tmp]);
tmp = t;
while(p[tmp]!=s) {
if(cost[tmp][p[tmp]]==ans) {
w = tmp;
h = p[tmp];
}
tmp = p[tmp];
}
if(cost[s][tmp]==ans) {
w = s;
h = tmp;
}
vis[w][h] = false;
vis[h][w] = false;
return ans;
}
int main()
{
int x, y, len, price;
while(scanf("%d%d", &n, &m)==2) {
if(n==0&&m==0) break;
memset(vis, false, sizeof(vis));
memset(d, -1, sizeof(d));
scanf("%d%d", &s, &t);
for(int i = 1; i <= m; i++) {
scanf("%d%d%d%d", &x, &y, &len, &price);
if(d[x][y]==-1) { // first time.
d[x][y] = len;
d[y][x] = len;
cost[x][y] = price;
cost[y][x] = price;
vis[x][y] = true;
vis[y][x] = true;
continue;
}
else if(d[x][y]==len) {
cost[x][y] += price; // 累计。
cost[y][x] += price;
}
else if(d[x][y]>len) {
d[x][y] = len;
d[y][x] = len;
cost[x][y] = price; // change.
cost[y][x] = price;
}
}
spfa();
int shortest = dis[t];
int res = work();
while(dis[t]==shortest) {
spfa();
int tmp = work();
if(dis[t]==shortest) {
res += tmp;
} else {
break;
}
}
printf("%d\n", res);
}
return 0;
}原文：http://blog.csdn.net/achiberx/article/details/23710847