题解

88 条题解

  • 0
    @ 2014-10-30 16:38:49

    Dijkstra,每次松弛时更新路径数组
    话说同样一份代码,关同步的cincout有四个点TLE,改成scanf和printf之后时间变成了原来的1/4,我记得两者的速度差别不是不大么……
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    #include<queue>
    using namespace std;
    const int INF = 0x7FFFFFFF;
    const int MAXN = 1011;
    struct Node
    {
    int d;
    int u;
    bool operator< (const Node &rhs) const
    {
    return d > rhs.d;
    }
    };
    struct Edge
    {
    int from, to, dis;
    };
    struct Dijkstra
    {
    int n, m;
    vector<int> g[MAXN];
    vector<int> path[MAXN];
    vector<Edge> edge;
    int d[MAXN];
    bool vis[MAXN];
    void init(int n)
    {
    this->n = n;
    for(int i = 0; i < MAXN; ++i)
    {
    g[i].clear();
    path[i].clear();
    }
    edge.clear();
    }
    void AddEdge(int from ,int to, int dis)
    {
    edge.push_back((Edge){from, to, dis});
    m = edge.size();
    g[from].push_back(m - 1);
    }
    void dijkstra(int s)
    {
    priority_queue<Node> q;
    fill(d, d + n + 1, INF);
    memset(vis, 0, sizeof(vis));
    q.push((Node){0, s});
    d[s] = 0;
    path[s].push_back(s);
    while(!q.empty())
    {
    Node cur = q.top(); q.pop();
    int u = cur.u;
    if(vis[u])continue;
    vis[u] = 1;
    for(int i = 0; i < g[u].size(); ++i)
    {
    Edge &e = edge[g[u][i]];
    if(d[e.to] > d[u] + e.dis)
    {
    d[e.to] = d[u] + e.dis;
    path[e.to].clear();
    for(int i = 0; i < path[u].size(); ++i)
    path[e.to].push_back(path[u][i]);
    path[e.to].push_back(e.to);
    q.push((Node){d[e.to], e.to});
    }
    }
    }
    }
    }dijks;
    int n;
    int main()
    {
    scanf("%d", &n);
    dijks.init(n);
    int tdis;
    for(int i = 0; i < n; ++i)
    for(int j = 0; j < n; ++j)
    {
    scanf("%d", &tdis);
    if(tdis == 0)continue;
    dijks.AddEdge(i, j, tdis);
    }
    dijks.dijkstra(0);
    vector<int> &p = dijks.path[n - 1];
    bool first = 1;
    for(int i = 0; i < p.size(); ++i)
    {
    if(first)
    {
    first = 0;
    printf("%d", p[i] + 1);
    }
    else printf(" %d", p[i] + 1);
    }
    printf("\n");
    printf("%d\n", dijks.d[n - 1]);
    return 0;
    }

    • @ 2014-10-30 16:41:57

      测试数据 #0: Accepted, time = 125 ms, mem = 5992 KiB, score = 15
      测试数据 #1: Accepted, time = 328 ms, mem = 11088 KiB, score = 15
      测试数据 #2: Accepted, time = 0 ms, mem = 784 KiB, score = 15
      测试数据 #3: Accepted, time = 328 ms, mem = 11100 KiB, score = 15
      测试数据 #4: Accepted, time = 15 ms, mem = 1364 KiB, score = 15
      测试数据 #5: Accepted, time = 296 ms, mem = 11244 KiB, score = 5
      测试数据 #6: Accepted, time = 15 ms, mem = 976 KiB, score = 5
      测试数据 #7: Accepted, time = 46 ms, mem = 2140 KiB, score = 5
      测试数据 #8: Accepted, time = 15 ms, mem = 1368 KiB, score = 5
      测试数据 #9: Accepted, time = 234 ms, mem = 11324 KiB, score = 5
      Accepted, time = 1402 ms, mem = 11324 KiB, score = 100

  • 0
    @ 2014-10-25 17:47:41

    测试数据 #0: Accepted, time = 62 ms, mem = 4540 KiB, score = 15
    测试数据 #1: Accepted, time = 140 ms, mem = 4544 KiB, score = 15
    测试数据 #2: Accepted, time = 15 ms, mem = 4544 KiB, score = 15
    测试数据 #3: Accepted, time = 156 ms, mem = 4540 KiB, score = 15
    测试数据 #4: Accepted, time = 15 ms, mem = 4540 KiB, score = 15
    测试数据 #5: Accepted, time = 109 ms, mem = 4548 KiB, score = 5
    测试数据 #6: Accepted, time = 0 ms, mem = 4544 KiB, score = 5
    测试数据 #7: Accepted, time = 15 ms, mem = 4544 KiB, score = 5
    测试数据 #8: Accepted, time = 15 ms, mem = 4544 KiB, score = 5
    测试数据 #9: Accepted, time = 109 ms, mem = 4544 KiB, score = 5
    Accepted, time = 636 ms, mem = 4548 KiB, score = 100
    ####代码
    program connection;
    var
    a:array[1..1000,1..1000] of longint;
    v:array[1..1000] of boolean;
    prev,dist,temp:array[1..1000] of longint;
    min:longint;
    n,i,j,l,tmp:integer;
    f:boolean;
    begin
    readln(n);
    fillchar(a,sizeof(a),0);
    for i:=1 to n do
    begin
    for j:=1 to n do
    begin
    read(a[i,j]);
    if (a[i,j]>0) and (i=1) then dist[j]:=a[i,j] else dist[j]:=maxlongint;
    end;
    if i=1 then prev[i]:=-1 else prev[i]:=1;
    readln;
    end;
    fillchar(v,sizeof(v),true);
    fillchar(temp,sizeof(temp),0);
    dist[1]:=0;v[1]:=false;
    repeat
    min:=maxlongint;l:=1;//Question
    for i:=1 to n do if v[i] and (dist[i]<min) then begin min:=dist[i];l:=i;end;
    v[l]:=false;
    for i:=1 to n do if (a[l,i]>0) and (dist[l]+a[l,i]<dist[i]) then begin dist[i]:=dist[l]+a[l,i];prev[i]:=l;end;
    f:=true;
    for i:=1 to n do if v[i] then begin f:=false;break;end;
    until f;
    tmp:=n;i:=1;
    while prev[tmp]<>-1 do
    begin
    temp[i]:=prev[tmp];
    i:=i+1;
    tmp:=prev[tmp];
    end;
    for j:=i-1 downto 1 do write(temp[j],' ');
    writeln(n);
    writeln(dist[n]);
    end.
    用Dijkstra求最短路径即可,但要加入prev数组记录最短路径节点。
    请教各位大神:程序中打Question的语句中为什么一定要l:=1;呢?我之前置l为0或不赋初始值都WA了,胡乱调试时令l=1就AC了。**求解释!!!**

  • 0
    @ 2014-03-01 22:39:57

    var n,i,j,tot:longint;
    a:array[0..1001,0..1001] of longint;
    f:array[0..1001] of int64;
    b:array[0..1001] of longint;
    function min(x,y:int64):int64;
    begin
    if x<y then exit(x) else exit(y);
    end;
    begin
    assign(input,'input10.txt');assign(output,'output.txt');
    reset(input);rewrite(output);
    readln(n);
    for i:=1 to n do
    begin
    for j:=1 to n do
    read(a[i,j]);
    readln;
    end;
    for i:=1 to n do f[i]:=maxlongint;
    f[1]:=0;
    for i:=2 to n do
    for j:=1 to i-1 do
    if a[j,i]<>0 then
    f[i]:=min(f[i],f[j]+a[j,i]);
    tot:=1;b[tot]:=n;
    for i:=n-1 downto 1 do
    if f[i]+a[i,n]=f[n] then
    begin
    inc(tot);b[tot]:=i;n:=i;
    end;
    for i:=tot downto 1 do write(b[i],' ');
    writeln;
    writeln(f[b[1]]);
    close(input);close(output);
    end.

  • 0
    @ 2014-02-15 18:04:35

    spfa

    测试数据 #0: Accepted, time = 124 ms, mem = 11996 KiB, score = 15
    测试数据 #1: Accepted, time = 265 ms, mem = 11988 KiB, score = 15
    测试数据 #2: Accepted, time = 15 ms, mem = 11996 KiB, score = 15
    测试数据 #3: Accepted, time = 218 ms, mem = 11992 KiB, score = 15
    测试数据 #4: Accepted, time = 0 ms, mem = 11988 KiB, score = 15
    测试数据 #5: Accepted, time = 202 ms, mem = 11992 KiB, score = 5
    测试数据 #6: Accepted, time = 0 ms, mem = 11988 KiB, score = 5
    测试数据 #7: Accepted, time = 31 ms, mem = 11996 KiB, score = 5
    测试数据 #8: Accepted, time = 15 ms, mem = 11992 KiB, score = 5
    测试数据 #9: Accepted, time = 156 ms, mem = 11992 KiB, score = 5
    Accepted, time = 1026 ms, mem = 11996 KiB, score = 100

    代码

    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<math.h>
    #define N 1000

    struct edge{
    int u,v,w;
    };

    struct point{
    int val;
    int in;
    int from;
    };

    struct edge edge[N*(N-1)];
    int u_index[N+1];
    int edge_r;
    struct point point[N];
    int stack[N],rear,front;
    int n,m;

    void push_on(int num,int val,int from)
    {
    point[num].val = val;
    point[num].from = from;
    if (!point[num].in) {
    point[num].in = 1;
    stack[rear++%N] = num;
    }
    }

    void out_stack()
    {
    point[stack[front++%N]].in = 0;
    }

    void add_edge(int u,int v,int w)
    {
    edge[edge_r].u = u;
    edge[edge_r].v = v;
    edge[edge_r++].w = w;
    }

    void set_index(int rear)
    {
    int i,u;
    i = 0; u = 0;
    while (u <= n) {
    while (i < rear)
    if (edge[i].u < u)
    i++;
    else
    break;
    u_index[u++] = i;
    }
    }

    void base_point()
    {
    int i,tmp;
    tmp = (1<<31)-1;
    front = rear = 0;
    for (i = 0;i < n;i++) point[i].in = 0;
    push_on(0,0,-1);
    for (i = 1;i < n;i++)
    push_on(i,tmp,-1);
    }

    void init()
    {
    int i,j,dis;
    scanf("%d",&n); m = n;
    edge_r = 0;
    for (i = 0;i < n;i++) {
    for (j = 0;j < m;j++) {
    scanf("%d",&dis);
    if (dis)
    add_edge(i,j,dis);
    }
    }
    set_index(edge_r);
    base_point();
    }

    void spfa()
    {
    int u,i,t,v;
    while (front < rear) {
    u = stack[front%N];
    for (i = u_index[u];i < u_index[u+1];i++) {
    v = edge[i].v;
    if (point[v].val > (t = point[u].val+edge[i].w))
    push_on(v,t,u);
    }
    out_stack();
    }
    }

    void print_path()
    {
    int rear,stack[N],v;
    rear = 0;
    v = stack[rear++] = n-1;
    while (point[v].from != -1)
    v = stack[rear++] =point[v].from;
    while (rear > 0)
    printf("%d ",stack[--rear]+1);
    printf("\n");
    }

    int main()
    {
    init();
    spfa();
    print_path();
    printf("%d\n",point[n-1].val);
    return 0;
    }

  • 0
    @ 2014-01-20 21:01:40

    评测结果
    编译成功

    foo.c: In function 'main':
    foo.c:86:1: warning: control reaches end of non-void function [-Wreturn-type]
    foo.c:46:11: warning: 'mn' may be used uninitialized in this function [-Wmaybe-uninitialized]
    测试数据 #0: Accepted, time = 124 ms, mem = 4408 KiB, score = 15
    测试数据 #1: Accepted, time = 218 ms, mem = 4404 KiB, score = 15
    测试数据 #2: Accepted, time = 0 ms, mem = 4412 KiB, score = 15
    测试数据 #3: Accepted, time = 156 ms, mem = 4408 KiB, score = 15
    测试数据 #4: Accepted, time = 31 ms, mem = 4408 KiB, score = 15
    测试数据 #5: Accepted, time = 249 ms, mem = 4412 KiB, score = 5
    测试数据 #6: Accepted, time = 15 ms, mem = 4408 KiB, score = 5
    测试数据 #7: Accepted, time = 31 ms, mem = 4408 KiB, score = 5
    测试数据 #8: Accepted, time = 15 ms, mem = 4408 KiB, score = 5
    测试数据 #9: Accepted, time = 249 ms, mem = 4412 KiB, score = 5
    Accepted, time = 1088 ms, mem = 4412 KiB, score = 100
    代码
    #include<stdio.h>
    #define M 199999999

    int n,way[1005][1005],plan[1005],flag[1005],pre[1005],ans[1000];

    int main()
    {
    // freopen("1635.in","r",stdin);
    int i,j,k,mn,min;
    scanf("%d",&n);
    k=n-2;
    for(i=1;i<=n;i++)
    {
    for(j=1;j<=n;j++)
    {
    scanf("%d",&way[i][j]);
    if(!way[i][j])
    {
    way[i][j]=M;
    }
    }
    }
    for(i=1;i<=n;i++)
    {
    plan[i]=way[1][i];
    pre[i]=1;
    }

    while(k)
    {
    k--;min=M;

    for(i=2;i<=n;i++)
    {
    if(flag[i])
    {
    continue;
    }

    if(min>plan[i])
    {
    min=plan[i];
    mn=i;
    }
    }
    flag[mn]=1;

    for(i=2;i<=n;i++)
    {
    if(flag[i])
    {
    continue;
    }

    if(plan[i]>plan[mn]+way[mn][i])
    {
    plan[i]=plan[mn]+way[mn][i];
    pre[i]=mn;
    }
    }
    }
    int tt=n;
    ans[1]=tt;
    for(i=2;i<=1000;i++)
    {
    tt=pre[tt];
    ans[i]=tt;
    if(tt==1)
    {
    break;
    }
    }
    for(;i;i--)
    {
    printf("%d",ans[i]);
    if(i!=1)
    {
    printf(" ");
    }
    else
    {
    printf("\n");
    }
    }
    printf("%d\n",plan[n]);
    }


    评测结果
    编译成功

    foo.cpp: In function 'int main()':
    foo.cpp:19:10: warning: unused variable 'k' [-Wunused-variable]
    foo.cpp:19:12: warning: unused variable 'mn' [-Wunused-variable]
    foo.cpp:19:15: warning: unused variable 'min' [-Wunused-variable]
    测试数据 #0: WrongAnswer, time = 109 ms, mem = 4412 KiB, score = 0
    测试数据 #1: WrongAnswer, time = 312 ms, mem = 4404 KiB, score = 0
    测试数据 #2: WrongAnswer, time = 0 ms, mem = 4412 KiB, score = 0
    测试数据 #3: WrongAnswer, time = 171 ms, mem = 4408 KiB, score = 0
    测试数据 #4: Accepted, time = 15 ms, mem = 4412 KiB, score = 15
    测试数据 #5: WrongAnswer, time = 140 ms, mem = 4412 KiB, score = 0
    测试数据 #6: Accepted, time = 0 ms, mem = 4412 KiB, score = 5
    测试数据 #7: WrongAnswer, time = 31 ms, mem = 4416 KiB, score = 0
    测试数据 #8: WrongAnswer, time = 31 ms, mem = 4408 KiB, score = 0
    测试数据 #9: WrongAnswer, time = 234 ms, mem = 4412 KiB, score = 0
    WrongAnswer, time = 1043 ms, mem = 4416 KiB, score = 20
    代码
    #include<stdio.h>
    #define M 199999999
    int n,way[1005][1005],plan[1005],q[1010],pre[1005],ans[1005];

    int ii(int x)
    {
    for(int i=0;i<n;i++)
    {
    if(q[i]==x)
    {
    return 1;
    }
    }
    return 0;
    }

    int main()
    {
    int i,j,k,mn,min;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
    for(j=1;j<=n;j++)
    {
    scanf("%d",&way[i][j]);
    if(!way[i][j])
    {
    way[i][j]=M;
    }
    }
    plan[i]=M;
    pre[i]=1;
    }
    plan[1]=0;
    q[0]=1;int tn=1,tp=0;
    while(tn)
    {
    tn--;
    int t=q[tn];
    for(i=1;i<=n;i++)
    {
    if(plan[t]+way[t][i]<plan[i])
    {
    plan[i]=plan[t]+way[t][i];
    pre[i]=t;
    if(!ii(i))
    {
    tp=(tp+1)%(n+5);
    tn++;
    q[tp]=i;
    }
    }
    }
    }
    int tt=n;
    ans[1]=tt;
    for(i=2;i<=1000;i++)
    {
    tt=pre[tt];
    ans[i]=tt;
    if(tt==1)
    {
    break;
    }
    }
    for(;i;i--)
    {
    printf("%d",ans[i]);
    if(i!=1)
    {
    printf(" ");
    }
    else
    {
    printf("\n");
    }
    }
    printf("%d\n",plan[n]);
    }


    为毛这么吊?
    7
    0 32 56 0 0 0 0
    0 0 0 64 8 55 0
    0 6 6 0 44 12 6
    15 6 0 0 0 0 4
    0 0 12 8 0 32 7
    0 0 0 0 0 0 11
    0 0 0 0 0 5 0

    WA掉的代码过了,A掉的代码错了,哇咧,为毛这么吊?

  • 0
    @ 2013-11-08 10:27:04

    var
    map:array[0..1000,0..1000] of longint;
    dis,pre:array[0..1000] of longint;
    flag:array[0..1000] of boolean;
    x,i,j,n,k:longint;
    procedure try(k:longint);
    begin
    if k=1 then
    begin
    write(1,' ');
    exit;
    end;
    try(pre[k]);
    write(k,' ');
    end;
    begin
    readln(n);
    fillchar(map,sizeof(map),\(7f);
    for i:=1 to n do
    begin
    for j:=1 to n do
    begin
    read(x);
    if x>0 then map[i,j]:=x;
    end;
    readln;
    end;
    fillchar(dis,sizeof(dis),\)7f);
    dis[1]:=0;
    while true do
    begin
    k:=0;
    for i:=1 to n do
    if not(flag[i]) and (dis[i]<dis[k]) then k:=i;
    flag[k]:=true;
    if k=0 then break;
    for i:=1 to n do
    if dis[k]+map[k,i]<dis[i] then
    begin
    dis[i]:=dis[k]+map[k,i];
    pre[i]:=k;
    end;
    end;
    try(n);
    writeln;
    writeln(dis[n]);
    end.
    明显的,n^2
    边这么多,老迪比老S更优。
    当然,要加一个pre记录路径,递归输出。
    PS:明天NOIP复赛,虽说普及组不考图论,但我还是练练手。

  • 0
    @ 2013-11-07 23:51:43

    floyd改单源?处理路径有点麻烦。。。
    var f:array[0..1000,0..1000]of longint;i,j,k,n:longint;w:array[0..1000,0..1000]of longint;way:array[0..1000]of longint;len:longint;
    procedure printf(n:longint);
    begin
    if w[1,n]=0 then begin inc(len,1);way[len]:=n;exit;end;
    inc(len,1);
    way[len]:=n;
    printf(w[1,n]);
    end;
    begin
    len:=0;
    fillchar(w,sizeof(w),0);
    readln(n);
    for i:=1 to n do
    for j:=1 to n do
    begin
    read(f[i,j]);
    if f[i,j]=0 then f[i,j]:=maxint;
    end;
    for j:=1 to n do
    for k:=1 to n do
    if (j<>k) then if f[1,k]+f[k,j]<f[1,j] then begin f[1,j]:=f[1,k]+f[k,j];w[1,j]:=k;end;
    printf(n);
    write(1,' ');
    for i:=len downto 1 do write(way[i],' ');
    writeln;
    writeln(f[1,n]);
    end.

  • 0
    @ 2013-07-29 10:48:00

    对这种程序能Ac表示无语。(某位大神说这程序有问题)

    #include<cstdio>
    struct gmh
    {
    int dis,fa;
    }f[2008];
    int n,min,p=0,a[2008],way[2008];
    int main()
    {
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++)
    {
    scanf("%d",&a[j]);
    if (a[j])
    if (f[j].dis==0 || f[j].dis>a[j]+f[i].dis)
    {
    f[j].dis=a[j]+f[i].dis;
    f[j].fa=i;
    }
    }
    for (int i=n;i;i=f[i].fa)
    {
    p++;
    way[p]=i;
    }
    for (int i=p;i>=1;i--)
    printf("%d ",way[i]);
    printf("\n%d",f[n].dis);
    return 0;
    }

  • 0
    @ 2013-07-11 20:26:14

    var
    a:array[0..1000,0..1000] of longint;
    b:array[1..1000,1..1000] of longint;
    dis:array[1..1000] of longint;
    pd:array[1..1000] of boolean;
    lb:array[1..1000] of longint;
    times:array[1..1000] of longint;
    q,d:array[1..1000] of longint;
    tot,i,j,k,n,m,x,y,z,h,t:longint;
    begin
    readln(n);
    for i:=1 to n do
    for j:=1 to n do
    begin
    read(b[i,j]);
    if b[i,j]<>0 then
    begin
    inc(a[i,0]);a[i,a[i,0]]:=j;
    end;
    end;
    dis[1]:=0; h:=0;t:=1;lb[1]:=1;
    for i:=2 to n do dis[i]:=maxlongint;
    while h<t do
    begin
    inc(h);
    x:=lb[h];
    for i:=1 to a[x,0] do
    if dis[a[x,i]]>dis[x]+b[x,a[x,i]] then
    begin
    dis[a[x,i]]:=dis[x]+b[x,a[x,i]];
    q[a[x,i]]:=x;
    if not pd[a[x,i]] then
    begin
    inc(t);
    lb[t]:=a[x,i];
    inc(times[a[x,i]]);
    pd[a[x,i]]:=true;
    end;
    end;
    pd[x]:=false;
    end;
    k:=n;
    while k>1 do
    begin
    inc(tot);
    d[tot]:=k;
    k:=q[k];
    end;
    write(1,' ');
    for i:=tot downto 2 do write(d[i],' '); writeln(d[1]);
    writeln(dis[n]);
    end.

  • 0
    @ 2013-07-08 00:12:18

    ###Block Code
    #include <iostream>
    #include <vector>
    #include <stack>
    #include <cstring>
    using namespace std;

    // GRAPH [Directed!]
    #define allocint(x,sz) {x=new int[sz];}
    class adjGraph
    {
    public:
    int n,m;
    int* firstlnk;
    int* lnknext,*lnkto,*lnkfro,*lnkw;
    adjGraph()
    {
    n=0;
    m=0;
    firstlnk=lnknext=lnkto=lnkfro=lnkw=NULL;
    }
    ~adjGraph()
    {
    if(n!=0&&m!=0)
    {
    delete firstlnk;
    delete lnkto;
    delete lnkfro;
    delete lnknext;
    delete lnkw;
    }
    }
    inline std::istream& input(std::istream& in)
    {
    int r,t,cur=0;
    in>>n;
    m=n*n;
    allocint(firstlnk,n);
    allocint(lnkto,m);
    allocint(lnkfro,m);
    allocint(lnkw,m);
    allocint(lnknext,m);
    memset(firstlnk,-1,n*sizeof(int));
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    {
    in>>r;
    if(r!=0)
    {
    t=firstlnk[i];
    firstlnk[i]=cur;
    lnknext[cur]=t;
    lnkto[cur]=j;
    lnkfro[cur]=i;
    lnkw[cur]=r;
    cur++;
    }
    }
    m=cur;
    return in;
    }
    };
    #define INF 1000000
    adjGraph base;

    // Dijkstra-------------------NOT SO FAMILIAR !
    int start;
    int end;
    int* father;
    int* d; //!!! NO NEED FOR the second dimension
    bool* visited;
    inline void init(int fro)
    {
    d=new int[base.n];
    visited=new bool[base.n];
    father=new int[base.n];
    for(int i=0;i<base.n;i++)
    d[i]=INF,visited[i]=false,father[i]=-1; //!!!! DON'T use lnkw to init d[]
    d[fro]=0;
    }
    inline int getsmallp()
    {
    int ans=-1;
    for(int i=0;i<base.n;i++)
    if(!visited[i]) //!!!! SET here as the place to check VISITED[] is more efficient
    {
    if(ans==-1) ans=i;
    else ans=(d[ans]>d[i])?i:ans;
    }
    return ans;
    }
    void Dijkstra(int fro)
    {
    init(fro);
    for(int i=0;i<base.n;i++)
    {
    int now=getsmallp();
    int t=base.firstlnk[now];
    visited[now]=true;
    while(t!=-1)
    {
    int u=base.lnkto[t];
    int w=base.lnkw[t];
    if(d[u]>d[now]+w)
    {
    d[u]=d[now]+w;
    /* !!!!!!!!!!!!!!! VERY !!!!!!!!!!!!!!!!!!! IMPORTANT !!!!!!!!!!
    if(father[u]==-1)
    father[u]=now;
    else father[u]=(father[u]>now)?now:father[u];*/
    father[u]=now;
    }
    t=base.lnknext[t];
    }
    }

    stack<int> help;
    help.push(end);
    int t=father[end];
    while(t!=-1)
    {
    help.push(t);
    t=father[t];
    }
    while(!help.empty())
    {
    t=help.top();help.pop();
    cout<<t+1<<' ';
    }
    cout<<endl<<d[end]<<endl;
    }

    int main()
    {
    cin.sync_with_stdio(false);
    base.input(cin);
    start=0;end=base.n-1;
    Dijkstra(start);
    return 0;
    }

  • 0
    @ 2013-07-08 00:11:25

    Dijkstra总算通过了,积累了一些经验。

    Jtwd2 via JudgeDaemon2/13.7.4.0 via libjudge
    编译成功

    测试数据 #0: Accepted, time = 249 ms, mem = 6340 KiB, score = 15
    测试数据 #1: Accepted, time = 655 ms, mem = 16144 KiB, score = 15
    测试数据 #2: Accepted, time = 15 ms, mem = 684 KiB, score = 15
    测试数据 #3: Accepted, time = 686 ms, mem = 15916 KiB, score = 15
    测试数据 #4: Accepted, time = 46 ms, mem = 1092 KiB, score = 15
    测试数据 #5: Accepted, time = 561 ms, mem = 13848 KiB, score = 5
    测试数据 #6: Accepted, time = 15 ms, mem = 824 KiB, score = 5
    测试数据 #7: Accepted, time = 93 ms, mem = 2848 KiB, score = 5
    测试数据 #8: Accepted, time = 31 ms, mem = 1188 KiB, score = 5
    测试数据 #9: Accepted, time = 530 ms, mem = 12548 KiB, score = 5
    Accepted, time = 2881 ms, mem = 16144 KiB, score = 100

    ###Block Code
    #include <iostream>
    #include <vector>
    #include <stack>
    #include <cstring>
    using namespace std;

    // GRAPH [Directed!]
    #define allocint(x,sz) {x=new int[sz];}
    class adjGraph
    {
    public:
    int n,m;
    int* firstlnk;
    int* lnknext,*lnkto,*lnkfro,*lnkw;
    adjGraph()
    {
    n=0;
    m=0;
    firstlnk=lnknext=lnkto=lnkfro=lnkw=NULL;
    }
    ~adjGraph()
    {
    if(n!=0&&m!=0)
    {
    delete firstlnk;
    delete lnkto;
    delete lnkfro;
    delete lnknext;
    delete lnkw;
    }
    }
    inline std::istream& input(std::istream& in)
    {
    int r,t,cur=0;
    in>>n;
    m=n*n;
    allocint(firstlnk,n);
    allocint(lnkto,m);
    allocint(lnkfro,m);
    allocint(lnkw,m);
    allocint(lnknext,m);
    memset(firstlnk,-1,n*sizeof(int));
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    {
    in>>r;
    if(r!=0)
    {
    t=firstlnk[i];
    firstlnk[i]=cur;
    lnknext[cur]=t;
    lnkto[cur]=j;
    lnkfro[cur]=i;
    lnkw[cur]=r;
    cur++;
    }
    }
    m=cur;
    return in;
    }
    };
    #define INF 1000000
    adjGraph base;

    // Dijkstra-------------------NOT SO FAMILIAR !
    int start;
    int end;
    int* father;
    int* d; //!!! NO NEED FOR the second dimension
    bool* visited;
    inline void init(int fro)
    {
    d=new int[base.n];
    visited=new bool[base.n];
    father=new int[base.n];
    for(int i=0;i<base.n;i++)
    d[i]=INF,visited[i]=false,father[i]=-1; //!!!! DON'T use lnkw to init d[]
    d[fro]=0;
    }
    inline int getsmallp()
    {
    int ans=-1;
    for(int i=0;i<base.n;i++)
    if(!visited[i]) //!!!! SET here as the place to check VISITED[] is more efficient
    {
    if(ans==-1) ans=i;
    else ans=(d[ans]>d[i])?i:ans;
    }
    return ans;
    }
    void Dijkstra(int fro)
    {
    init(fro);
    for(int i=0;i<base.n;i++)
    {
    int now=getsmallp();
    int t=base.firstlnk[now];
    visited[now]=true;
    while(t!=-1)
    {
    int u=base.lnkto[t];
    int w=base.lnkw[t];
    if(d[u]>d[now]+w)
    {
    d[u]=d[now]+w;
    /* !!!!!!!!!!!!!!! VERY !!!!!!!!!!!!!!!!!!! IMPORTANT !!!!!!!!!!
    if(father[u]==-1)
    father[u]=now;
    else father[u]=(father[u]>now)?now:father[u];*/
    father[u]=now;
    }
    t=base.lnknext[t];
    }
    }

    stack<int> help;
    help.push(end);
    int t=father[end];
    while(t!=-1)
    {
    help.push(t);
    t=father[t];
    }
    while(!help.empty())
    {
    t=help.top();help.pop();
    cout<<t+1<<' ';
    }
    cout<<endl<<d[end]<<endl;
    }

    int main()
    {
    cin.sync_with_stdio(false);
    base.input(cin);
    start=0;end=base.n-1;
    Dijkstra(start);
    return 0;
    }

  • 0
    @ 2013-06-20 16:56:59

    #include <cstdio>
    #include <algorithm>
    #include <queue>
    #include <cstdlib>
    #include <cstring>
    using namespace std;
    struct P{
    int s,t,val;
    }data[1000005];
    queue<int> QUE;
    int P,a,b=1;
    int S[2001],dis[2001],cnt,pre[2001];
    void solve();
    void print(int);
    int main(){
    freopen("1.in","r",stdin);
    scanf("%d",&P);
    for(int i=1;i<=P;i++)
    for(int j=1;j<=P;j++){
    scanf("%d",&a);
    if(a!=0) data[b].s=i,data[b].t=j,data[b].val=a,S[i]++,b++;
    }
    for(int i=1;i<=b;i++) S[i]=b+1;
    for(int i=b;i>0;i--) S[data[i].s]=i;
    for(int i=0;i<=P;i++) if(S[i+1]==b+1) S[i+1]=S[i];
    for(int i=1;i<=P;i++) dis[i]=0xfffffff;
    int a;

    a=1;
    dis[a]=0;
    QUE.push(a);
    solve();
    print(pre[P]);
    printf("%d\n%d",P,dis[P]);

    }
    void print(int p)
    {
    if(p==0) return;
    print(pre[p]);
    printf("%d ",p);
    }
    void solve(){
    while(!QUE.empty()){
    int tmp=QUE.front();
    QUE.pop();
    for(int i=S[tmp];i<S[tmp+1];i++){
    if(dis[data[i].t] > dis[tmp]+data[i].val)
    dis[data[i].t]=dis[tmp]+data[i].val,pre[data[i].t]=tmp,QUE.push(data[i].t);
    }
    }
    }
    全部RE掉了 求解

  • 0
    @ 2013-06-20 16:50:12

    求助大神 为什么都WA掉了呢
    求数据范围

  • 0
    @ 2010-04-16 12:41:00

    var i,j,n,s,t:longint;

      a:array[0..1000,0..1000] of longint;

      f,q:array[0..1000] of longint;

    begin

    readln(n);

    for i:=1 to n do

    for j:=1 to n do

    read(a);

    for i:=1 to n-1 do

    f[i]:=maxlongint;

    for i:=n-1 downto 1 do

    for j:=i+1 to j do

    begin

    if (a>0) and (a+f[j]

  • 0
    @ 2010-03-08 16:51:11

    var i,j,n,s,t:longint;

    a:array[0..1000,0..1000] of longint;

    f,q:array[0..1000] of longint;

    begin

    readln(n);

    for i:=1 to n do

    for j:=1 to n do

    read(a);

    for i:=1 to n-1 do

    f[i]:=maxlongint;

    for i:=n-1 downto 1 do

    for j:=i+1 to j do

    begin

    if (a>0) and (a+f[j]

  • 0
    @ 2009-11-10 18:43:24

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    唉,还得细心啊!!

  • 0
    @ 2009-11-09 21:25:32

    floyed秒杀......

  • 0
    @ 2009-11-09 20:52:41

    第一先输路径,第二是有向边,第三,任何时候都要细心,冷静。

  • 0
    @ 2009-11-08 13:43:10

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 72ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:72ms

    var q:array[0..100000]of longint;

    b:array[0..1003]of boolean;

    dis,route:array[0..1003]of longint;

    a:array[0..1003,0..1003]of longint;

    n,x,y,w,m:longint;

    procedure init;

    var i,j:longint;

    begin

    readln(n);

    for i:=1 to n do

    for j:=1 to n do

    begin

    read(a);

    if a=0 then a:=99999999;

    end;

    end;

    procedure find(k:longint);

    begin

    if k0 then

    begin

    find(route[k]);

    write(k,' ');

    end;

    end;

    procedure spfa;

    var i,x,l,r:longint;

    begin

    q[1]:=1;

    l:=1;

    r:=1;

    for i:=1 to n do route[i]:=0;

    for i:=2 to n do dis[i]:=99999999;

    dis[1]:=0;

    fillchar(b,sizeof(b),false);

    b[1]:=true;

    while l

  • 0
    @ 2009-11-04 23:50:18

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 119ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 88ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:207ms

    难得一次AC...好水的题...不过复习了一下DIJKSTRA的路径处理

信息

ID
1635
难度
5
分类
图结构 | 最短路 点击显示
标签
(无)
递交数
3419
已通过
1138
通过率
33%
被复制
2
上传者