# 19 条题解

• @ 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]);
}
}
``````
• @ 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]));
}
}
}
``````
• @ 2017-09-30 20:49:11

很H2O的题

• @ 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;
}

• @ 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;
}
```

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

果然水题要细心2333

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

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

• @ 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;
{
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()
{
memset(f,63,sizeof(f));
memset(d,63,sizeof(d));
//初始化，自己到自己的距离是0;
for(ll i=1;i<=m;i++)
{
ll x,y,z;
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]);
//在枚举每一个加油点，找最小答案
while(Q--)
{
printf("%lld\n",f[S][T]);
}
return 0;
}

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

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

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

最后一个点卡SPFA？

• @ 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;
}
``````
• @ 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;
}

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

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

• @ 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)

这服务器怎么了，怎么了

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

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

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

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

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

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

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

• @ 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

32

for i:=1 to q do

33

begin

34

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])

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

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

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

u,v为起点与终点。

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

注意判断-1。

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

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

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

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

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

• 1

ID
1746

5

(无)

899

287

32%

2