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:这题不科学啊，同样的数据，两个ac掉的代码跑出来的不一样啊 (4724) 1917 2014-04-25 18:55:26
  • Re:这题不科学啊，同样的数据，两个ac掉的代码跑出来的不一样啊 (11) hkj_fh 2014-06-08 21:16:04
• Re:这题不科学啊，同样的数据，两个ac掉的代码跑出来的不一样啊 (10) 1917 2014-04-25 18:56:01
  • Re:这题不科学啊，同样的数据，两个ac掉的代码跑出来的不一样啊 (22) hkj_fh 2014-06-09 15:27:00
• Re:这题不科学啊，同样的数据，两个ac掉的代码跑出来的不一样啊 (4724) Yzx835 2015-11-05 15:40:58
  • Re:600 (0) Yzx835 2015-11-05 15:41:11
• Re:这题不科学啊，同样的数据，两个ac掉的代码跑出来的不一样啊 (12) Jason224413 2017-08-08 15:12:37
• Re:严格与非严格的区别 (16) ibilllee 2018-06-26 15:06:29
• Re:这题不科学啊，同样的数据，两个ac掉的代码跑出来的不一样啊 (4724) zuotimmp 2019-03-08 18:09:45