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

Re:SPFA+二维数组记录

Posted by FlyAlone at 2011-08-08 11:28:56 on Problem 1724 and last updated at 2011-08-08 11:29:30
In Reply To:SPFA+二维数组记录 Posted by:yanqing at 2011-07-13 17:31:12
> #include <cstdio>
> #include <cstdlib>
> #define oo 2147483647
> int n,kk,m;
> struct node{
>     int x,len,w,next;
> }e[10010];
> int k[110];
> int tot;
> int d[110][10000];
> int f[1000000];
> bool v[110];
> void add(int a,int b,int c,int d){
>      e[++tot].x=b;
>      e[tot].len=c;
>      e[tot].w=d;
>      e[tot].next=k[a];
>      k[a]=tot;
> }
> void spfa(){
>      int head=0,tail=1;
>      for (int i=2;i<=n;i++)
>      for (int j=0;j<=kk;j++)
>          d[i][j]=2147483;     
>      v[1]=true;
>      f[tail]=1;
>      while (head<tail){
>            int x=f[++head];
>            v[x]=false;
>            for (int t=k[x];t;t=e[t].next){
>                int to=e[t].x;
>                for (int i=e[t].w;i<=kk;i++){
>                    if (d[to][i]>d[x][i-e[t].w]+e[t].len){
>                        d[to][i]=d[x][i-e[t].w]+e[t].len;
>                        if (!v[to]){
>                                    v[to]=true;
>                                    f[++tail]=to;
>                        }
>                    }
>                }
>            }
>      }
> }
> int main(){
>     scanf("%d%d%d",&kk,&n,&m);
>     for (int i=1;i<=m;i++){
>         int a,b,c,d;
>         scanf("%d%d%d%d",&a,&b,&c,&d);
>         add(a,b,c,d);
>     }
>     spfa();
>     int max=oo;
>     for (int i=0;i<=kk;i++)
>         if (d[n][i]<max) max=d[n][i];
>     if (max==oo) printf("-1\n");else printf("%d\n",max);
>     //system("pause");
>     return 0;
> }
>     
能否讲下思路?

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator