/ Vijos / 题库 / 小D的旅行 /

题解

19 条题解

  • 5
    @ 2017-06-29 22:06:44

    两次FLOYD，一次最短路，一次加上加油

    #include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,m,q,s[400][400],f[400][400],w[400];
int main(){
    scanf("%d%d",&n,&m); 
    memset(s,63,sizeof s);
    memset(f,63,sizeof f);
    for(int i=1;i<=n;++i) scanf("%d",w+i),s[i][i]=0;
    for(int x,y,z,i=0;i<m;++i){
        scanf("%d%d%d",&x,&y,&z);
        s[x][y]=min(s[x][y],z);
        s[y][x]=min(s[y][x],z);
    }
    for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j) 
                s[i][j]=min(s[i][j],s[i][k]+s[k][j]);
    for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j) 
                f[i][j]=min(f[i][j],s[i][k]+w[k]+s[k][j]);
    scanf("%d",&q);
    for(int x,y,i=0;i<q;++i){
        scanf("%d%d",&x,&y);
        printf("%d\n",f[x][y]);
    }
}
  • 2
    @ 2017-09-30 20:48:45 
    #include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,m,q;
int v[300+1];
int c[300+1][300+1];
int d[300+1][300+1];

int main()
{
    while (~scanf("%d%d",&n,&m))
    {
        for (int i=1;i<=n;i++)
            scanf("%d",&v[i]);
        memset(c,oo_max,sizeof(c));
        memset(d,oo_max,sizeof(d));
        for (int i=1;i<=m;i++)
        {
            int x,y,w;
            scanf("%d%d%d",&x,&y,&w);
            d[x][y]=d[y][x]=min(w,min(d[x][y],d[y][x]));
        }
        for (int i=1;i<=n;i++)
            d[i][i]=0;
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                for (int k=1;k<=n;k++)
                    d[j][k]=min(d[j][k],d[j][i]+d[i][k]);
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                for (int k=1;k<=n;k++)
                    c[j][k]=min(c[j][k],d[j][i]+d[i][k]+v[i]);
        scanf("%d",&q);
        for (int i=1;i<=q;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%d\n",min(c[x][y],c[y][x]));
        }
    }
}
  • 1
    @ 2019-02-12 15:53:48

    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<queue>
    #include<stack>
    using namespace std;
    int main()
    {
    int n,m;
    int a,b,w,f[400][400];
    memset(f,0x3f,sizeof(f));
    scanf("%d%d",&n,&m);
    int v[n];
    for(int i=1;i<=n;i++)
    {
    scanf("%d",&v[i]);
    f[i][i]=0;
    }
    for(int i=1;i<=m;i++)
    {
    scanf("%d%d%d",&a,&b,&w);
    f[a][b]=min(f[a][b],w);
    f[b][a]=min(f[b][a],w);
    }
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    if(f[i][j]>f[i][k]+f[k][j])
    {
    f[i][j]=f[i][k]+f[k][j];
    }
    int u[400][400];
    memset(u,0x3f,sizeof(u));
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    if(u[i][j]>f[i][k]+f[k][j]+v[k])
    {
    u[i][j]=f[i][k]+f[k][j]+v[k];
    }
    int q;
    scanf("%d",&q);
    while(q--)
    {
    scanf("%d%d",&a,&b);
    printf("%d\n",u[a][b]);
    }
    return 0;
    }

  • 1
    @ 2016-12-02 23:54:31

    评测结果
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 1512 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 1516 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 1512 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 1520 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 1516 KiB, score = 10
    测试数据 #5: Accepted, time = 15 ms, mem = 1520 KiB, score = 10
    测试数据 #6: Accepted, time = 15 ms, mem = 1520 KiB, score = 10
    测试数据 #7: Accepted, time = 78 ms, mem = 1520 KiB, score = 10
    测试数据 #8: Accepted, time = 15 ms, mem = 1520 KiB, score = 10
    测试数据 #9: Accepted, time = 46 ms, mem = 1516 KiB, score = 10
    Accepted, time = 184 ms, mem = 1520 KiB, score = 100
    代码
    ```c++
    #include<iostream>
    #include<iomanip>
    #include<cstring>
    #include<vector>
    #include<sstream>
    #include<algorithm>
    #include<string>
    #include<cstdio>
    #include<math.h>
    #include<cctype>
    #include<vector>
    #include<queue>
    #include<functional>
    #define maxn 350
    #define INF 1000000
    #define min(a,b) (a)>(b)?(b):(a)
    #define Mem(a,b) memset((a),(b),sizeof((a)))
    using namespace std;

    int n, m;
    int map[maxn][maxn];
    int p[maxn][maxn];
    int w[maxn];
    int main(){
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i += 1){
    scanf("%d", &w[i]);
    }
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
    p[i][j] = map[i][j] = INF;
    for (int i = 1; i <= m; i += 1){
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    if (a != b)
    map[a][b] = map[b][a] = min(min(map[b][a],map[a][b]),c);
    }
    for (int k = 1; k <= n; k += 1)
    for (int i = 1; i <= n; i += 1)
    for (int j = 1; j <= n; j += 1)
    map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
    for (int i = 1; i <= n; i++)
    map[i][i] = 0;

    for (int k = 1; k <= n; k += 1)
    for (int i = 1; i <= n; i += 1)
    for (int j = 1; j <= n; j += 1)
    p[i][j] = p[j][i] = min(p[i][j], map[i][k] + map[k][j] + w[k]);
    int c;
    scanf("%d", &c);
    for (int i = 0; i < c; i += 1){
    int a, b;
    scanf("%d %d", &a, &b);
    if (p[a][b] < INF)
    printf("%d\n", p[a][b]);
    else
    printf("-1\n");
    }/*
    system("pause");*/
    return 0;
    }
    ```

  • 1
    @ 2016-08-20 12:03:24

    果然水题要细心2333

  • 1
    @ 2012-10-28 20:36:53

    为嘛非要两边弗洛伊德来？一边做完直接枚举加油站不就行了吗。

  • 0
    @ 2017-10-20 21:12:41

    一开始上来没看数据范围，直接就是SPFA，结果直接就打残了，只有20分。
    后来看了数据范围，果断换了Floyd，以后一定要学乖，最短路问题先看数据范围
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    #include<cstring>
    #include<queue>
    #include<map>
    #include<string>
    #define ll long long
    #define inf 214748364
    #define DB double
    using namespace std;
    inline ll read()
    {
    ll x=0,w=1;char ch=0;
    while(ch<'0' || ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*w;

    }
    ll tot,n,m,w[3000];
    ll f[400][400],Q;
    ll d[400][400],S,T;
    int main()
    {
    n=read();m=read();
    memset(f,63,sizeof(f));
    memset(d,63,sizeof(d));
    for(ll i=1;i<=n;i++) w[i]=read(),d[i][i]=0;
    //初始化，自己到自己的距离是0;
    for(ll i=1;i<=m;i++)
    {
    ll x,y,z;
    x=read();y=read();z=read();
    d[x][y]=d[y][x]=min(d[x][y],z);
    }
    for(ll k=1;k<=n;k++)
    for(ll i=1;i<=n;i++)
    for(ll j=1;j<=n;j++)
    d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    //先求出不加加油费的最短距离
    for(ll k=1;k<=n;k++)
    for(ll i=1;i<=n;i++)
    for(ll j=1;j<=n;j++)
    f[i][j]=min(f[i][j],d[i][k]+w[k]+d[k][j]);
    //在枚举每一个加油点，找最小答案
    Q=read();
    while(Q--)
    {
    S=read();T=read();
    printf("%lld\n",f[S][T]);
    }
    return 0;
    }

  • 0
    @ 2016-08-13 14:30:56

    floyd 水过。。。
    先求出两点之间的最近距离，再枚举在哪个点加油。。。

  • 0
    @ 2016-08-11 13:43:38

    最后一个点卡SPFA？

  • 0
    @ 2016-04-12 23:50:55

    注意不是一定从最短路上加油，比如2到2，费用=0+邮费[2]。
    但是2的邮费贵了，选择跑到3加个油再回到2，更优。

    由于询问对较多，选择2遍FLOYD。

    #include <cstdio>
#include <cstring>
#define INF 999999999
//#define debug

int n,m;
int price[310];
int map[310][310];
int map2[310][310];

void build(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&price[i]);
    }
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            map[i][j]=INF;
        } 
            
    int u,v,val;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&val);
        if(u==v)
            continue;           //去自环
        map[u][v]=map[u][v]<val?map[u][v]:val;
        map[v][u]=map[v][u]<val?map[v][u]:val;
    }
}

void floyd(){
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        if(map[i][k]+map[k][j]<map[i][j])
            map[i][j]=map[i][k]+map[k][j];          
}

void floyd2(){  
    for(int i=1;i<=n;i++)
        map[i][i]=0;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        map2[i][j]=INF; 
    for(int k=1;k<=n;k++)       //选择 k点加油 
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        if(map[i][k]+map[k][j]+price[k]<map2[i][j])
            map2[i][j]=map[i][k]+map[k][j]+price[k];        
}

int main(){
#ifdef debug
    freopen("in.txt","r",stdin);
//  freopen("out.txt","w",stdout);
#endif
    build();
    floyd();
    floyd2();
    int p,p1,p2;
    scanf("%d",&p);
    for(int i=1;i<=p;i++){
        scanf("%d%d",&p1,&p2);
        printf("%d\n",map2[p1][p2]);
    }
    return 0;
}
  • 0
    @ 2015-07-05 23:13:25

    P1746小D的旅行
    Accepted

    记录信息

    评测状态 Accepted
    题目 P1746 小D的旅行
    递交时间 2015-07-05 23:12:52
    代码语言 C++
    评测机 VijosEx
    消耗时间 432 ms
    消耗内存 996 KiB
    评测时间 2015-07-05 23:12:54

    评测结果

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 996 KiB, score = 10

    测试数据 #1: Accepted, time = 0 ms, mem = 992 KiB, score = 10

    测试数据 #2: Accepted, time = 15 ms, mem = 992 KiB, score = 10

    测试数据 #3: Accepted, time = 15 ms, mem = 992 KiB, score = 10

    测试数据 #4: Accepted, time = 15 ms, mem = 996 KiB, score = 10

    测试数据 #5: Accepted, time = 15 ms, mem = 996 KiB, score = 10

    测试数据 #6: Accepted, time = 15 ms, mem = 992 KiB, score = 10

    测试数据 #7: Accepted, time = 218 ms, mem = 996 KiB, score = 10

    测试数据 #8: Accepted, time = 46 ms, mem = 996 KiB, score = 10

    测试数据 #9: Accepted, time = 93 ms, mem = 992 KiB, score = 10

    Accepted, time = 432 ms, mem = 996 KiB, score = 100

    代码

    #include <iostream>
    #include <stdio.h>

    using namespace std;

    int i , j , k;
    int n , m;
    int v[300 + 2];
    int w[300 + 2][300 + 2];
    int q;
    int x , y , t;
    int a[300 + 2][300 + 2];

    int min( int a , int b )
    {
    if( a > b )
    return b;
    return a;
    }

    void floyd()
    {
    for( k = 1 ; k <= n ; k++ )
    for( i = 1 ; i <= n ; i++ )
    for( j = 1 ; j <= n ; j++ )
    w[i][j] = w[j][i] = min( w[i][j] , w[i][k] + w[k][j] );
    for( k = 1 ; k <= n ; k++ )
    for( i = 1 ; i <= n ; i++ )
    for( j = 1 ; j <= n ; j++ )
    {
    a[i][j] = min( a[i][j] , w[i][k] + w[k][j] + v[k] );
    a[i][j] = min( a[i][j] , w[i][k] + a[k][j] );
    a[i][j] = min( a[i][j] , a[i][k] + w[k][j] );
    }
    return;
    }

    int main()
    {
    scanf( "%d %d" , &n , &m );
    for( i = 1 ; i <= n ; i++ )
    scanf( "%d" , &v[i] );
    for( i = 1 ; i <= n ; i++ )
    for( j = 1 ; j <= n ; j++ )
    {
    w[i][j] = 1000000;
    a[i][j] = 1000000;
    if( i == j )
    {
    w[i][j] = 0;
    a[i][j] = v[i];
    }
    }
    for( i = 0 ; i < m ; i++ )
    {
    scanf( "%d %d %d" , &x , &y , &t );
    w[x][y] = min( w[x][y] , t );
    w[y][x] = w[x][y];
    }
    floyd();
    scanf( "%d" , &q );
    for( i = 0 ; i < q ; i++ )
    {
    scanf( "%d %d" , &x , &y );
    if( a[x][y] < 1000000 )
    printf( "%d\n" , a[x][y] );
    else
    printf( "-1\n" );
    }
    //system( "pause" );
    return 0;
    }

  • 0
    @ 2014-10-30 11:18:31

    这题目说不清不楚给跪了- - 还是我语文太差？ 大概的意思是求一条最短路 并且在这个路的途中选择一个加油站加油使代价最小 还以为每经过一个城市都要加一次油 什么破车啊→→

  • 0
    @ 2012-11-01 09:28:10

    第一交

    #01: ---|---|---|---|---|---|---|---|-

    Accepted (35ms, 1284KB) 

    #02: ---|---|---|---|---|---|---|---|-

    Accepted (35ms, 1284KB) 

    #03: ---|---|---|---|---|---|---|---|-

    Accepted (39ms, 1284KB) 

    #04: ---|---|---|---|---|---|---|---|-

    Accepted (59ms, 1284KB) 

    #05: Time Limit Exceeded (?, 1212KB) 

    #06: ---|---|---|---|---|---|---|---|-

    Accepted (55ms, 1284KB) 

    #07: ---|---|---|---|---|---|---|---|-

    Accepted (59ms, 1284KB) 

    #08: ---|---|---|---|---|---|---|---|-

    Accepted (157ms, 1284KB) 

    #09: Time Limit Exceeded (?, 1212KB) 

    #10: ---|---|---|---|---|---|---|---|-

    Accepted (153ms, 1284KB) 

    第二交

    #01: Time Limit Exceeded (?, 1212KB) 

    #02: ---|---|---|---|---|---|---|---|-

    Accepted (953ms, 1284KB) 

    #03: Time Limit Exceeded (?, 1212KB) 

    #04: Time Limit Exceeded (?, 1212KB) 

    #05: ---|---|---|---|---|---|---|---|-

    Accepted (67ms, 1284KB) 

    #06: ---|---|---|---|---|---|---|---|-

    Accepted (51ms, 1284KB) 

    #07: ---|---|---|---|---|---|---|---|-

    Accepted (47ms, 1284KB) 

    #08: Time Limit Exceeded (?, 1212KB) 

    #09: ---|---|---|---|---|---|---|---|-

    Accepted (78ms, 1284KB) 

    #10: ---|---|---|---|---|---|---|---|-

    Accepted (75ms, 1284KB) 

    第三交

    #01: ---|---|---|---|---|---|---|---|-

    Accepted (47ms, 1284KB) 

    #02: ---|---|---|---|---|---|---|---|-

    Accepted (39ms, 1284KB) 

    #03: ---|---|---|---|---|---|---|---|-

    Accepted (59ms, 1284KB) 

    #04: ---|---|---|---|---|---|---|---|-

    Accepted (35ms, 1284KB) 

    #05: ---|---|---|---|---|---|---|---|-

    Accepted (51ms, 1284KB) 

    #06: ---|---|---|---|---|---|---|---|-

    Accepted (51ms, 1284KB) 

    #07: ---|---|---|---|---|---|---|---|-

    Accepted (47ms, 1284KB) 

    #08: ---|---|---|---|---|---|---|---|-

    Accepted (149ms, 1284KB) 

    #09: ---|---|---|---|---|---|---|---|-

    Accepted (67ms, 1284KB) 

    #10: ---|---|---|---|---|---|---|---|-

    Accepted (137ms, 1284KB) 

    这服务器怎么了，怎么了

  • 0
    @ 2012-10-31 18:49:33

    通过的第88人&&本人一百题~

  • 0
    @ 2012-10-28 18:02:10

    不是很难的图论题，做的时候抽了。。。两遍floyd，一遍单纯求两点之间的最短路，另一遍用另一个数组存储加上加油费用后两点之间的权值

    （f:=min(f,d+d[k,j]+a[k]),1

  • 0
    @ 2012-10-28 16:34:02

    一种建模思路：点数变为2*n，后n个点为加过油的，连边，前n个点到后n个点的边要算上加油的费用，floyd，对于每个询问输出d

  • 0
    @ 2012-10-28 10:10:46

    ├ 测试数据 01：答案正确... (55ms, 1284KB) 

    ├ 测试数据 02：答案正确... (51ms, 1284KB) 

    ├ 测试数据 03：答案正确... (63ms, 1284KB) 

    ├ 测试数据 04：答案正确... (35ms, 1284KB) 

    ├ 测试数据 05：答案正确... (71ms, 1284KB) 

    ├ 测试数据 06：答案正确... (51ms, 1284KB) 

    ├ 测试数据 07：答案正确... (86ms, 1284KB) 

    ├ 测试数据 08：答案正确... (172ms, 1284KB) 

    ├ 测试数据 09：答案正确... (71ms, 1284KB) 

    ├ 测试数据 10：答案正确... (35ms, 1284KB) 

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

    Accepted / 100 / 695ms / 1284KB 

    view sourceprint?

    01

    var

    02

      g,f:array[1..300,1..300]of longint;

    03

      a:array[1..300]of longint;

    04

      n,m,i,x,y,z,k,j,q,ans:longint;

    05

    function min(x,y:longint):longint;

    06

    begin

    07

      if xz)then f[x,y]:=z;

    17

        if (f[y,x]=-1)or(f[y,x]>z)then f[y,x]:=z;

    18

      end;

    19

      for i:=1 to n do f:=0;

    20

      for i:=1 to n do

    21

      for j:=1 to n do g:=min(a[i],a[j]);

    22

      for k:=1 to n do

    23

      for i:=1 to n do

    24

      if f>=0 then

    25

      for j:=1 to n do

    26

      if f[k,j]>=0 then

    27

      begin

    28

        if f=-1 then f:=f+f[k,j]

    29

        else if f>f+f[k,j] then f:=f+f[k,j];

    30

      end;

    31

      read(q);

    32

      for i:=1 to q do

    33

      begin

    34

        read(x,y);

    35

        if f[x,y]=-1 then writeln(-1)

    36

        else

    37

        begin

    38

          ans:=f[x,y]+g[x,y];

    39

          for j:=1 to n do

    40

          if (f[x,j]+f[j,y]+min(g[x,j],g[j,y])

  • 0
    @ 2012-10-28 09:34:05

    第一次floyd求出所有点之间的最短路。

    枚举一点作为加油站，设为k点。

    u,v为起点与终点。

    求出 f+f[k,v]+p[k]的最小值即可。

    注意判断-1。

  • 0
    @ 2012-10-28 07:07:19

    两遍FLOYD，第一次先求出两两点之间的最短路，用最简单的FLOYD算法即可。

    然后，再用一个N^3的循环将以某一个点做加油站的路径求出来即可，表示我语文从来没有及过格，描述可能相当不清晰。

    欢迎来我的空间参考代码，看了代码之后，就很清晰了。。。

    http://hi.baidu.com/samroxas/item/4c8ae49f89c0b931336eebfe

  • 1

小D的旅行

信息

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