SDUT 周赛 2498 AOE网上的关键路径-白红宇

SDUT 周赛 2498 AOE网上的关键路径

阅读量：6643 次

发布时间：2019-06-25

本文共 2022 字，大约阅读时间需要 6 分钟。

题意：汉语...

思路：

比赛的时候是按spfa正向的处理的，然后记录每一点的前一个点如果出现相等去最小的那个。结果wa。赛后才知道这样处理时错的。

比如下图：如果现在终点是6，现在2和3都能使6的距离达到最大且值相同。我们处理的时候会选2，但还是2这条路径却不是最优的，反而3是最有的。

所以我们逆向见图，求一个最短路然后倒着输出就好了。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define CL(a,num) memset((a),(num),sizeof(a))#define iabs(x) ((x) > 0 ? (x) : -(x))#define Min(a,b) (a) > (b)? (b):(a)#define Max(a,b) (a) > (b)? (a):(b)#define ll long long#define inf 0x7f7f7f7f#define MOD 1073741824#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define test puts("<------------------->")#define maxn 100007#define M 50007#define N 10007using namespace std;//freopen("din.txt","r",stdin);struct node{ int v,w; int next;}g[M];int head[N],ct;struct mm{ int x,y;}p[M];int pre[N];int vt[N];int dis[N];int id[N],cd[N];int n;void add(int u,int v,int w){ g[ct].v = v; g[ct].w = w; g[ct].next = head[u]; head[u] = ct++;}void spfa(int s){ int i,j; for (i = 1; i <= n; ++i) { dis[i] = -inf; vt[i] = false; pre[i] = -1; } queue
                
                 q; q.push(s); dis[s] = 0; vt[s] = true; while (!q.empty()) { int u = q.front(); q.pop(); for (i = head[u]; i != -1; i = g[i].next) { int v = g[i].v; int w = g[i].w; if (dis[v] < dis[u] + w) { pre[v] = u; dis[v] = dis[u] + w; if (!vt[v]) { vt[v] = true; q.push(v); } } else if (dis[v] == dis[u] + w && pre[v] != -1 && pre[v] > u) { pre[v] = u; if (!vt[v]) { vt[v] = true; q.push(v); } } } vt[u] = false; }}int main(){ //freopen("din.txt","r",stdin); int m; int i; int u,v,w; while (~scanf("%d%d",&n,&m)) { CL(head,-1); ct = 0; CL(id,0); CL(cd,0); for (i = 0; i < m; ++i) { scanf("%d%d%d",&u,&v,&w); add(v,u,w); id[u]++; cd[v]++; } int s,e; for (i = 1; i <= n; ++i) { if (id[i] == 0) s = i; if (cd[i] == 0) e = i; } // printf("%d %d\n",s,e); spfa(s); printf("%d\n",dis[e]); int x = e; int len = 0; while (x != s) { printf("%d %d\n",x,pre[x]); len++; x = pre[x]; } } return 0;}

转载地址：http://ksevo.baihongyu.com/

你可能感兴趣的文章