/ Vijos / 题库 / 最短路上的统计 /

题解

131 条题解

  • 0
    @ 2008-10-02 12:37:58

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    floyd预处理,然后枚举中点k(K可以与I,J是同一个点);

    ANS初始化为0;

    if dis+dis[k,j]=dis then inc(ans);

    1

  • 0
    @ 2008-09-29 21:51:16

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    秒杀！！！

  • 0
    @ 2008-09-29 20:56:59

    好冷的题目 TAT!!!!!!!!!!!!!!!

    Conan 你怎么今年才出这道题

  • 0
    @ 2008-09-26 19:16:21

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    FLOYD 就可以0s通过，太假了。。。

  • 0
    @ 2008-09-23 13:17:07

    编译通过...

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

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

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

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

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

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

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

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

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

    ├ 测试数据 10：答案正确... 88ms

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

    Accepted 有效得分：100 有效耗时：88ms

    我开始弄错了题意，以为如果有好多条最短路相交，就把重复的点重复几遍算几遍。实际上是每个点顶多算一遍。否则按我的理解就比较麻烦了。

  • 0
    @ 2008-09-22 17:32:07

    楼下好样的,我记录更新的次数就是只有30分,郁闷

  • 0
    @ 2008-09-22 16:58:01

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

    floyd后 ，读入（a,b），当d[a,i]＋d=d[a,b]（１＜＝Ｉ＜＝Ｎ）　累加　sum，输出sum即为解个数

  • 0
    @ 2008-09-20 22:05:15

    floyd+记解...

  • 0
    @ 2008-09-20 08:39:53

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    真无语　刚开始用dijkstra写的　老是不过　后来用floyd随便一写就过了　我的通过率呀～～～～～

  • 0
    @ 2008-09-19 19:09:55

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

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

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

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

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

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

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

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

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

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

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

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

    貌似不难,FLOYD改了一点点.

  • 0
    @ 2008-09-19 13:49:54

    Floyd

  • 0
    @ 2008-09-17 20:19:41

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    Floyd

  • 0
    @ 2008-09-17 18:39:34

    编译通过...├ 测试数据 01：答案正确... 0ms├ 测试数据 02：答案正确... 0ms├ 测试数据 03：答案正确... 0ms├ 测试数据 04：答案正确... 0ms├ 测试数据 05：答案正确... 0ms├ 测试数据 06：答案正确... 0ms├ 测试数据 07：答案正确... 0ms├ 测试数据 08：答案正确... 0ms├ 测试数据 09：答案正确... 0ms├ 测试数据 10：答案正确... 181msvar n,m,p:longint; f:array[1..100,1..100]of longint; g:array[1..100,1..100,1..100]of boolean; b:array[1..10000,1..2]of longint;procedure init;var i,j,k:longint;beginfilldword(f,sizeof(f) div 4,100000); readln(n,m); for i:=1 to m do begin readln(j,k); f[j,k]:=1; f[k,j]:=1; g[j,k,j]:=true; g[j,k,k]:=true; g[k,j]:=g[j,k]; end; readln(p); for i:=1 to p do readln(b,b);end;procedure main;var i,j,k,t:longint;begin for k:=1 to n do for i:=1 to n do for j:=i+1 to n do begin t:=f+f[k,j]; if t=f then for t:=1 to n do g:=g or g[k,j,t] or g; if t

  • 0
    @ 2008-09-16 23:38:13

    编译通过...

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

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

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

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

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

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

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

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

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

    ├ 测试数据 10：答案正确... 41ms

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

    Accepted 有效得分：100 有效耗时：41ms

    未连接点初始复制为maxlongint

    floyd后

    for(q=q;q>=1;q--)

    {

    cin>>i>>j;

    sum=2;

    for(k=1;k

  • 0
    @ 2008-09-16 12:42:16

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    呜呼，我说不出话，但以此纪念刘和珍君！

  • 0
    @ 2008-09-15 21:08:04

    如果，，

    郁闷死了，，如果不是昨天出去吃饭，，只有40分钟时间。。

    呜呜·

    那就有260分的！！！

    今天一次就AC了一道题目。。

    别说我胡吹，，我问心无愧！我自己做的！用了1个小时，什么都没看，当考试一样。，！

    昨天只有40分钟做！

    以神的速度做了两道。。150

    加油！大牛！

  • 0
    @ 2008-09-15 16:37:09

    编译通过...

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

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

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

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

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

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

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

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

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

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

    咱觉得还是咱的比较精妙点儿

    const Infinite=1000000000;

    binary:array[0..32]of longword=(2147483648,1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648);

    sort:array[1..100]of smallint=(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,4,4,4,4);

    type rectype=array[1..4]of longword;

    var n,m,q:longint;

    dist:array[1..100,1..100]of longint;

    cross:array[1..100,1..100]of rectype;

    procedure init;

    var i,j,a,b:longint;

    begin

    readln(n,m);

    for i:=1 to n do

    for j:=1 to n do

    dist:=Infinite;

    for i:=1 to m do

    begin

    readln(a,b);

    dist[a,b]:=1;

    dist:=1;

    cross[a,b,sort[a]]:=binary[a mod 32];

    cross[a,b,sort]:=cross[a,b,sort] or binary[b mod 32];

    cross:=cross[a,b];

    end;

    end;

    procedure print(a,b:longint);

    var i,j,res:longint;

    begin

    res:=0;

    for i:=1 to 3 do

    for j:=1 to 32 do

    if binary[j] and cross[a,b,i]>0 then

    inc(res);

    for j:=1 to 4 do

    if binary[j] and cross[a,b,4]>0 then

    inc(res);

    writeln(res);

    end;

    procedure main;

    var i,j,k,p:longint;

    begin

    for k:=1 to n do

    for i:=1 to n do

    for j:=1 to n do

    if dist+dist[k,j]

  • 0
    @ 2008-09-15 17:11:44

    编译通过...

  • 0
    @ 2008-09-15 16:02:44

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2008-09-15 14:36:34

    我只会DFS。。会超吧？

最短路上的统计

信息

ID
1446
难度
5
分类
图结构 | 最短路 点击显示
标签
递交数
3509
已通过
1328
通过率
38%
被复制
10
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1