Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 这题不科学啊，同样的数据，两个ac掉的代码跑出来的不一样啊

Posted by 201293123 at 2013-04-10 23:38:33 on Problem 3255
```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
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];
void spfa (int source, int *dist)
{
vector *p;
int cur, tar, l, i;

for (i = 0; i < n; i++)
dist[i] = MAX;
dist[source] = 0;
{
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;
}
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;
}

#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];
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;
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;
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);
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].x=line[i*2-1].y; line[i*2].y=line[i*2-1].x; line[i*2].w=line[i*2-1].w;
}
r*=2;
djikstra();
printf("%d\n",Astar());
return 0;
}

Followed by: