重过1最短路题 写个了另一种方法的

重过一最短路题 写个了另一种方法的

最近好像有点浮躁

mle是内存超限不是输出超限

还有addedge时要注意某些自己到自己的边不要重复  有可能造成死循环。

#include <iostream>#include <cstdio>#include <cstring>#include <vector>#include <set>#include <queue>using namespace std;//尼玛二维数组定义成一维的也报错也报那种错误。。擦啊。。。const int maxn = 5000, INF = 10000000;int input[maxn][maxn];//int hehe[maxn][maxn];int str1[maxn], str2[maxn];  //用于遍历int node[maxn];int dis[maxn];struct Edge{    int from, to, dist;};int n;vector<Edge> edges;vector<int> G[maxn];bool inq[maxn];  //队列优化spfa判断是否边已加入int d[maxn];int p[maxn];    //最短路中的上一条弧//int is_neg[maxn];  //进队次数  用于判断是否有负权环void init(){    for(int i = 0;i < n;i++) G[i].clear();    edges.clear();}void addedge(int from, int to, int dist)  //单向边操作{    edges.push_back((Edge){from, to, dist});    int len = edges.size();    G[from].push_back(len - 1);}void spfa(int be)  //可返回bool判断负权环{    memset(inq, 0, sizeof(inq));    memset(p, 0, sizeof(p));    //memset(is_neg, 0, sizeof(is_neg));  //注释用于判断负环    queue<int> Q;    for(int i = 0;i < n;i++)       d[i] = INF;    d[be] = 0;    Q.push(be);    inq[be] = true;    while(!Q.empty())  //  非空~    {        int u = Q.front(); Q.pop();        inq[u] = false;        for(int i = 0;i < G[u].size();i++)        {            Edge &e = edges[G[u][i]];            if(d[e.to] > d[u] + e.dist)  //这地方把想要输入的值已经转化为e.dist了            {                d[e.to] = d[u] + e.dist;                p[e.to] = u;      //G[u][i]存的是一条边的信息哪不存在标号 直接改成u                if(!inq[e.to])                {                    Q.push(e.to);                    inq[e.to] = true;                    // if(++is_neg[e.to] > n) return true;                }            }            else if(d[e.to] == d[u] + e.dist)            {                  int l1=0, l2=0;                  int temp = e.to;                  while(temp != be)                  {                      str1[l1++] = temp;                      temp = p[temp];                  }                  temp=u;                  while(temp!=be)                  {                      str2[l2++]=temp;                      temp=p[temp];                  }                  for(int i=l1-1,j=l2-1;i>=0&&j>=0;i--,j--)                  {                      if(str1[i]>str2[j])                      {                          p[e.to]=u;                          break;                      }                      else if(str1[i]<str2[j]) break;                  }                  if(!inq[e.to])                  {                     inq[e.to]=true;                     Q.push(e.to);                  }              }        }    }    //return false;}int main(){    int a,b;    while(scanf("%d",&n)!=EOF)    {        if(!n) break;        for(int i=0;i<n;i++)         for(int j=0;j<n;j++)         {            scanf("%d",&input[i][j]);         }        for(int i=0;i<n;i++) scanf("%d",&node[i]);        //memset(hehe, INF, sizeof(hehe));        for(int i = 0;i < n;i++)            for(int j = 0;j < n;j++)            {                if(input[i][j] == -1) input[i][j] = INF;                else if(input[i][j] == 0) input[i][j] = 0;                else  input[i][j] = input[i][j] + node[j];            }        init();  //清空函数        for(int i = 0;i < n;i++)            for(int j = 0;j < n;j++)            {                if(i != j)                    addedge(i, j, input[i][j]);            }        while(scanf("%d%d",&a,&b))        {             if(a==-1 && b==-1)break;             if(a==b)             {                 printf("From %d to %d :\nPath: %d\nTotal cost : 0\n\n",a,b,a);                 continue;             }             a--;b--;             spfa(a);             int l=0;    int x=b;             while(p[x]!=a)             {                 dis[l++]=p[x];                 x=p[x];             }             printf("From %d to %d :\nPath: %d-->",a+1,b+1,a+1);             for(int i=l-1;i>=0;i--)             {                 printf("%d-->",dis[i]+1);             }             printf("%d\nTotal cost : %d\n\n",b+1,d[b]-node[b]);         }    }    return 0;}