POJ 3259 Wormholes

这个题意就是利用虫洞时光倒流，题目中给出的虫洞史有向边！

SPFA水过~~这个跑了204ms 第一次写应该是邻接矩阵的缘故……sad

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cstdlib>
  4 
  5 using namespace std;
  6 
  7 const int INF = (1<<20);
  8 
  9 
 10 int dis[100000];
 11 
 12 struct N
 13 {
 14     int u,v,w;
 15     struct N *next;
 16 }*head[510];
 17 
 18 void link(int u,int v,int w)
 19 {
 20     N *p;
 21     p = (struct N *)malloc(sizeof(struct N));
 22     p->next = NULL;
 23     p->w = w;
 24     p->v = v;
 25     p->next = head[u]->next;
 26     head[u]->next = p;
 27 }
 28 
 29 void init(int n)
 30 {
 31     for(int i = 1; i <= n; i++)
 32     {
 33         head[i] = (struct N *)malloc(sizeof(struct N));
 34         head[i]->v = -1;
 35         head[i]->next = NULL;
 36     }
 37 }
 38 
 39 int q[100001];
 40 int mark[510];
 41 
 42 bool spfa(int n)
 43 {
 44     for(int k = 1; k <= n; k++)
 45     {
 46         N *p;
 47         int s = 0,e = 0,i;
 48         for(i = 1; i <= n; i++)
 49             mark[i] = 0;
 50         mark[k] = 1;
 51         q[e++] = k;
 52         while(s != e)
 53         {
 54             int t = q[s++];
 55 
 56             for(p = head[t]->next; p != NULL; p = p->next)
 57             {
 58                 if(dis[p->v] - p->w > dis[t])
 59                 {
 60                     if(mark[p->v] < n)
 61                     {
 62                         dis[p->v] = dis[t] + p->w;
 63                         mark[p->v]++;
 64                         q[e++] = p->v;
 65                     }
 66                     else
 67                         return true;
 68                 }
 69             }
 70 
 71 
 72             if(s == 100001) s = 0;
 73             if(e == 100001) e = 0;
 74         }
 75     }
 76     return false;
 77 }
 78 
 79 int main()
 80 {
 81     int js,n,m,w,i,e,u,v,t;
 82     scanf("%d",&js);
 83     while(js--)
 84     {
 85         scanf("%d %d %d",&n,&m,&w);
 86 
 87         init(n);
 88 
 89         for(i = 1; i <= n; i++)
 90             dis[i] = INF;
 91 
 92         for(i = 0; i < m; i++)
 93         {
 94             scanf("%d %d %d",&u,&v,&t);
 95             link(u,v,t);
 96             link(v,u,t);
 97         }
 98 
 99         for(i = 0; i < w; i++)
100         {
101             scanf("%d %d %d",&u,&v,&t);
102             link(u,v,-t);
103         }
104 
105         if(spfa(n))
106             printf("YES\n");
107         else printf("NO\n");
108 
109 
110     }
111     return 0;
112 }

这个是bellman ford 跑了63ms……

#include<cstdio>
#include<cstring>
#include<cstdlib>

using namespace std;

const int INF = (1<<20);

struct N
{
    int s,e,t;
}edge[100000];

int dis[100000];

bool bell_man(int n,int e)
{
    bool flag;
    for(int i = 0;i < n-1; i++)
    {
        flag = false;
        for(int j = 0;j < e; j++)
            if(dis[edge[j].e] > dis[edge[j].s] + edge[j].t)
            {
                dis[edge[j].e] = dis[edge[j].s] + edge[j].t;
                flag = true;
            }
        if(!flag)
            break;
    }
    for(int k = 0;k < e; k++)
        if(dis[edge[k].e] > dis[edge[k].s] + edge[k].t)
            return true;
    return false;
}

int main()
{
    int js,n,m,w,i,e,u,v,t;
    scanf("%d",&js);
    while(js--)
    {
        scanf("%d %d %d",&n,&m,&w);
        
        for(i = 1;i <= n; i++)
            dis[i] = INF;
        
        for(e = 0,i = 0;i < m; i++)
        {
            scanf("%d %d %d",&u,&v,&t);
            edge[e].s = edge[e+1].e = u;
            edge[e].e = edge[e+1].s = v;
            edge[e].t = edge[e+1].t = t;
            e += 2;
        }
        
        for(i = 0;i < w; i++)
        {
            scanf("%d %d %d",&u,&v,&t);
            edge[e].s = u;
            edge[e].e = v;
            edge[e].t = -t;
            e++;
        }
        
        if(bell_man(n,e))
            printf("YES\n");
        else printf("NO\n");
    
    }
    return 0;
}