Layout(spfa+差分约束）

View Code
  1 #include<iostream>
  2 #include<cstring>
  3 using namespace std;
  4 
  5 const int MAXN=1010;
  6 const int M=20020;
  7 const int INF=0x3f3f3f3f;
  8 int head[MAXN];//每个结点的头指针
  9 int vis[MAXN];//在队列标志
 10 int cnt[MAXN];//每个点的入队列次数
 11 int que[MAXN];//SPFA循环指针
 12 int dist[MAXN];
 13 
 14 struct Edge
 15 {
 16     int to;
 17     int v;
 18     int next;
 19 }edge[M];
 20 int tol;
 21 void add(int a,int b,int v)//加边
 22 {
 23     edge[tol].to=b;
 24     edge[tol].v=v;
 25     edge[tol].next=head[a];
 26     head[a]=tol++;
 27 }
 28 bool spfa(int start,int n)
 29 {
 30     int front=0,rear=0;
 31     for(int v=1;v<=n;v++)//初始化
 32     {
 33         if(v==start)
 34         {
 35             que[rear++]=v;
 36             vis[v]=true;
 37             cnt[v]=1;
 38             dist[v]=0;
 39         }
 40         else
 41         {
 42             vis[v]=false;
 43             cnt[v]=0;
 44             dist[v]=INF;
 45         }
 46     }
 47     while(front!=rear)
 48     {
 49         int u=que[front++];
 50         vis[u]=false;
 51         if(front>=MAXN)front=0;
 52         for(int i=head[u];i!=-1;i=edge[i].next)
 53         {
 54             int v=edge[i].to;
 55             if(dist[v]>dist[u]+edge[i].v)
 56             {
 57                 dist[v]=dist[u]+edge[i].v;
 58                 if(!vis[v])
 59                 {
 60                     vis[v]=true;
 61                     que[rear++]=v;
 62                     if(rear>=MAXN)rear=0;
 63                     if(++cnt[v]>n) return false;
 64                     //cnt[i]为入队列次数，用来判断是否存在负环回来
 65                     //这条好像放在这个if外面也可以？？
 66                 }
 67             }
 68         }
 69     }
 70     return true;
 71 }
 72 int main()
 73 {
 74     int n;
 75     int ML,MD;
 76     int a,b,c;
 77     while(cin>>n>>ML>>MD)
 78     {
 79         tol=0;//加边计数，这个不要忘
 80         memset(head,-1,sizeof(head));
 81         while(ML--)
 82         {
 83             cin>>a>>b>>c ;
 84             if(a>b)swap(a,b);//注意加边顺序
 85             add(a,b,c);
 86             //大-小<=c ,有向边(小，大）：c
 87         }
 88         while(MD--)
 89         {
 90             cin>>a>>b>>c ;
 91             if(a<b)swap(a,b);
 92             add(a,b,-c);
 93             //大-小>=c,小-大<=-c,有向边(大，小):-c
 94         }
 95         if(!spfa(1,n))
 96         cout<<"-1"<<endl ;//无解
 97         else
 98         if(dist[n]==INF)
 99         cout<<"-2"<<endl ;
100         else cout<<dist[n]<<endl ;
101     }
102     return 0;
103 }
还不是很明白，参考的