> 5 6
> 1 2 100
> 2 3 100
> 3 4 100
> 4 5 100
> 3 5 200
> 2 5 700
> 
> #include <stdio.h>
> #define QR 65536
> #define MAX 0x7FFFFFFF
> /* POJ 3255: Roadblocks */
> typedef struct str_vec
> {
>     int to;
>     int length;
>     struct str_vec *next;
> } vector;
> vector chain[5100];
> int side_a[100100], side_b[100100], side_l[100100];
> int dist_0[5100];
> int dist_n[5100];
> int queue[QR], add, now, n;
> void spfa (int source, int *dist)
> {
>     vector *p;
>     int cur, tar, l, i;
>     
>     add = now = 0;
>     queue[add++] = source;
>     for (i = 0; i < n; i++)
>         dist[i] = MAX;
>     dist[source] = 0;
>     while (now != add)
>     {
>         cur = queue[(now++) % QR];
>         p = (chain + cur)->next;
>         while (p != NULL)
>         {
>             tar = p->to;
>             l = p->length;
>             if (dist[cur] + l < dist[tar])
>             {
>                 dist[tar] = dist[cur] + l;
>                 queue[(add++) % QR] = tar;
>             }
>             p = p->next;
>         }
>     }
>     return;
> }
> int main ()
> {
>     int m, i, st, ed, len, ans = MAX, sp, sn;
>     vector *p, *r;
>     
>     scanf("%d %d", &n, &m);
>     
>     for (i = 0; i < n; i++)
>         chain[i].to = i, chain[i].next = NULL;
>         
>     for (i = 0; i < m; i++)
>     {
>         scanf("%d %d %d", &st, &ed, &len);
>         st--, ed--;
>         side_a[i] = st, side_b[i] = ed, side_l[i] = len;
>         
>         r = chain + st;
>         while (r->next != NULL) r = r->next;
>         p = (vector *)malloc(sizeof(vector));
>         p->to = ed, p->length = len, p->next = NULL;
>         r->next = p;
>         
>         r = chain + ed;
>         while (r->next != NULL) r = r->next;
>         p = (vector *)malloc(sizeof(vector));
>         p->to = st, p->length = len, p->next = NULL;
>         r->next = p;
>     }
>     
>     spfa(0, dist_0);
>     spfa(n - 1, dist_n);
>     sp = dist_0[n - 1];
>     
>     for (i = 0; i < m; i++)
>     {
>         st = side_a[i], ed = side_b[i], len = side_l[i];
>         sn = dist_0[st] + len + dist_n[ed];
>         if (sn != sp && sn < ans) ans = sn;
>         sn = dist_0[ed] + len + dist_n[st];
>         if (sn != sp && sn < ans) ans = sn;
>     }
>     
>     printf("%d\n", ans);
>     //system("pause");
>     
>     return 0;
> }
> 这跑出来是600
> 
> 
> 
> #include<iostream>
> #include<queue>
> #define MAXN 200001
> #include<string.h>
> #include<stdio.h>
> using namespace std;
> struct node
> {
>      int h,g,p;
>      bool operator < (node a) const
>      {
>           return a.h+a.g<h+g;
>      }
> };
> struct nodeOfLine
> {
>      int x,y,w,next;
> }line[MAXN];
> int n,r,link[5001],g[5001];
> priority_queue<node> myqueue;
> void djikstra()
> {
>     int i,j,k,t;
>     bool used[MAXN];
>     memset(g,0x7F,sizeof(g));
>     memset(used,false,sizeof(used));
>     g[n]=0;
>     for (t=1;t<=n;t++)
>     {
>          j=0;
>          for (i=1;i<=n;i++)
>            if (!used[i] && (!j || g[i]<g[j])) j=i;
>          used[j]=true;
>          k=link[j];
>          while (k)
>          {
>               if (g[line[k].y]>g[line[k].x]+line[k].w)
>                    g[line[k].y]=g[line[k].x]+line[k].w;
>               k=line[k].next;
>          }
>     }
>     return;
> }
> int Astar()
> {
>     node h,temp;
>     int times[5001],k;
>     while (!myqueue.empty()) myqueue.pop();
>     memset(times,0,sizeof(times));
>     h.p=1; h.h=h.g=0;
>     myqueue.push(h);
>     while (!myqueue.empty())
>     {
>           h=myqueue.top();
>           myqueue.pop();
>           times[h.p]++;
>           if (times[h.p]>2) continue;
>           if (times[h.p]==2 && h.p==n) return h.h+h.g;
>           k=link[h.p];
>           while (k)
>           {
>                 temp.p=line[k].y;
>                 temp.h=h.h+line[k].w;
>                 temp.g=g[line[k].y];
>                 myqueue.push(temp);
>                 k=line[k].next;
>           }
>     }
>     return -1;
> }
> int main()
> {
>     scanf("%d%d",&n,&r);
>     memset(link,0,sizeof(link));
>     for (int i=1;i<=r;i++)
>     {
>           scanf("%d%d%d",&line[i*2-1].x,&line[i*2-1].y,&line[i*2-1].w);
>           line[i*2-1].next=link[line[i*2-1].x]; link[line[i*2-1].x]=i*2-1;
>           line[i*2].x=line[i*2-1].y; line[i*2].y=line[i*2-1].x; line[i*2].w=line[i*2-1].w;
>           line[i*2].next=link[line[i*2].x]; link[line[i*2].x]=i*2;
>     }
>     r*=2;
>     djikstra();
>     printf("%d\n",Astar());
>     return 0;
> }
> 
> 
> 
> 这跑出来是400
> 不科学啊

• Re:600 (0) Yzx835 2015-11-05 15:41:11