本文共 2404 字，大约阅读时间需要 8 分钟。
#include#include #include #include using namespace std;#define MAX 1005#define INF 9999999int pre[MAX];int d[MAX];int head[MAX];int used[MAX][MAX];//1表示有效边 0表示无效边 bool marked[MAX];int dis[MAX];struct Edge{ int from, to, w; int next; };Edge edge[MAX*MAX];int n,m;int tol;int spfa() { queue que; for(int i = 1; i <= n; i++ ){ dis[i] = INF; marked[i] = false; } dis[1] = 0; marked[1] = true; que.push(1); while(!que.empty()){ int cur = que.front(); que.pop(); marked[cur] = false; for(int i = head[cur]; i != -1; i = edge[i].next){ int v = edge[i].to; if(dis[v] > dis[cur] + edge[i].w){ dis[v] = dis[cur] + edge[i].w; pre[v] = cur; if(!marked[v]){ que.push(v); marked[v] = true; } } } } return dis[n]; } int work() { queue que; for(int i = 1; i <= n; i++ ){ dis[i] = INF; marked[i] = false; } dis[1] = 0; marked[1] = true; que.push(1); while(!que.empty()){ int cur = que.front(); que.pop(); marked[cur] = false;//需要 及时置为false for(int i = head[cur]; i != -1; i = edge[i].next){ int v = edge[i].to; if(used[cur][v] && dis[v] > dis[cur] + edge[i].w){//与spfa区分 当最短路上某条边阻塞失效时 的最短路 dis[v] = dis[cur] + edge[i].w; if(!marked[v]){ que.push(v); marked[v] = true; } } } } return dis[n]; } void addEdge(int from, int to, int w) { edge[tol].next = head[from]; edge[tol].from = from; edge[tol].to = to; edge[tol].w = w; head[from] = tol++; }int main() { while(scanf("%d%d",&n,&m)!=EOF){ tol = 0; memset(head,-1,sizeof(head)); memset(used,0,sizeof(used)); pre[1] = -1; int a,b,c; for(int i = 0; i < m; i++ ){ scanf("%d%d%d",&a,&b,&c); used[a][b] = 1; used[b][a] = 1; addEdge(a,b,c); addEdge(b,a,c); } int ans = spfa();//阻塞路不在最短路上时候 最短路 for(int i = n; pre[i] != -1; i = pre[i]){// 对最短路上的每一条边遍历（当当前边阻塞时候最短路） used[i][pre[i]] = 0; //找到 这其中最长的路 used[pre[i]][i] = 0; int res = work(); if(res > ans){ ans = res; } used[i][pre[i]] = 1;//模拟完当前边为阻塞路径后及时 恢复有效边 继续模拟其它最短路上的边 used[pre[i]][i] = 1; } printf("%d\n",ans); } return 0; }
注意：Runtime Error (ACCESS_VIOLATION（G++提交时候） 换为c++则直接报错
可能 原因：
runtime error （运行时错误）就是程序运行到一半，程序就崩溃了。
比如说： ①除以零 ②数组越界：int a[3]; a[10000000]=10;（考虑数组开小了） ③指针越界：int * p; p=(int *)malloc(5 * sizeof(int)); *(p+1000000)=10; ④使用已经释放的空间：int * p; p=(int *)malloc(5 * sizeof(int));free(p); *p=10; ⑤数组开得太大，超出了栈的范围，造成栈溢出：int a[100000000];转载地址：http://llimi.baihongyu.com/