对于如下输入
4 4
1 2 1
2 3 2
3 4 3
1 4 4

你的程序输出为6，但正确的输出应该是4吧？


> Uva开始比赛了，把我的代码先给你看看吧.....
> 
> // Solution by richard
> // shortest path problem,courtesy of Dijkstra
> 
> #include <stdio.h>
> #include <string.h>
> 
> struct node
> {
>   int vto,v;
>   int next;
> };
> 
> struct edge
> {
>   int s,t;
>   int v;
> };
> 
> struct node matrix[1<<18];
> struct edge heap[1<<18];
> int d[65536/2],visit[65536/2];
> int tail=0;
> int bi;
> int n,m;
> 
> void fix_up()
> {
>   int i,k;
>   struct edge p;
> 
>   i=tail;
>   p=heap[i];
>   while (i>1) {
>     k=i/2;
>     if (heap[k].v>p.v) heap[i]=heap[k];
>     else break;
>     i=k;
>   }
>   heap[i]=p;
> }
> 
> void fix_down()
> {
>   int i,k;
>   struct edge p;
>   
>   i=1;
>   p=heap[1];
>   while (i<=tail/2) {
>     k=i*2;
>     if (k<tail && heap[k+1].v<heap[k].v) ++k;
>     heap[i]=heap[k];
>     i=k;
>   }
>   heap[i]=p;
> }
> 
> void insert(int s,int t,int v)
> {
>   heap[++tail].s=s;
>   heap[tail].t=t;
>   heap[tail].v=v;
>   fix_up();
> }
> 
> struct edge get()
> {
>   struct edge p=heap[1];
> 
>   heap[1]=heap[tail--];
>   fix_down();
>   return p;
> }
> 
> void construct(int s,int t,int v)
> {
>   matrix[bi].next=matrix[s].next;
>   matrix[s].next=bi;
>   matrix[bi].vto=t;
>   matrix[bi++].v=v;
> }
> 
> void get_edges(int s)
> {
>   int i;
> 
>   i=matrix[s].next;
>   while (i) {
>     insert(s,matrix[i].vto,matrix[i].v);
>     i=matrix[i].next;
>   }
> }
> 
> void read_data()
> {
>   int i;
>   int a,b,c;
> 
>   for (i=0;i<m;++i) {
>     scanf("%d %d %d",&a,&b,&c);
>     construct(a,b,c);
>   }
> }
> 
> void solve()
> {
>   struct edge e;
> 
>   visit[1]=1;
>   get_edges(1);
>   while (tail) {
>     e=get();
>     if (!visit[e.t]) {
>       visit[e.t]=1;
>       get_edges(e.t);
>       d[e.t]=d[e.s]+e.v;
>     }
>   }
>   
>   printf("%d\n",d[n]);
> }
> 
> int main()
> {
>   scanf("%d %d",&n,&m);
>   bi=n+1;
>   read_data();
>   solve();
>   return 0;
> }

• 正确答案是4,我的代码发给你了 (0) TopBoy 2007-01-21 10:17:20