「JoyOI1510」专家复仇
背景 Background
外星人完成对S国的考察后，准备返回，可他们的飞碟已经没燃料了……
S国的专家暗自窃喜……复仇的机会终于来了——他们打算敲诈外星人一大笔钱……
描述 Description
S国有n个燃料基地，保存有外星人所需的全部燃料，编号分别为1,2,3,…,n，对于每个燃料基地i，都有「((i-1) mod 10)+1」吨燃料。其中，编号<=5的燃料基地两两之间都有可双向通行的路；对于其余每个燃料基地i，与(i-1),(i-3)之间，也有可双向通行的路。对于任意两燃料基地i,j，若之间有路将他们「直接」连接，则通过这条路的运费为「(i*j)mod10+(i+j)mod6+1)」(单位：元/吨)。
S国的专家要按每吨一元的价格把燃料卖给外星人，并且要它们支付运费。那么，外星人应选择把所有燃料运往那个燃料基地，才能尽可能的让S国专家失望？它们所要支付的最小费用是多少？
注：数据保证解的唯一性。
输入格式 InputFormat
仅有一个整数n。
输出格式 OutputFormat
第一行：外星人所要支付的最小费用；
第二行：可供外星人选择的燃料基地的编号。
数据范围和注释 Hint
样例解释：
第1-5个基地两两间有路，第6个基地与第3,5个基地间有路。当把全部燃料运到第五个基地时，总费用最少，为107.
数据范围：
对于 30%的数据，有5<N<50;
对于 60%的数据，有5<N<500;
对于100%的数据，有5<=N<700;
输出数据范围请大家自行判断。
题解
这题可以用来练习打表，但是由于数据水你懂得
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include<iostream> #include<cstdio> #include<cstring> #define inf 100000000 using namespace std; int n,b[701]; int d[701][701]; int dis(int x,int y) { if(y<x)swap(x,y); if(x==y)return 0; if(y>5&&y-x!=1&&y-x!=3)return inf; return (x*y)%10+(x+y)%6+1; } int work(int x) { for(int i=1;i<=x;i++)for(int j=1;j<=x;j++)d[i][j]=dis(i,j); for(int k=1;k<=x;k++) for(int i=1;i<=x;i++) for(int j=1;j<=x;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]); int ans=inf; for(int i=1;i<=x;i++) { d[i][0]=0; for(int j=1;j<=x;j++) { if(d[j][i]==inf){d[i][0]=-1;break;} int t=(j-1)%10+1; d[i][0]+=t*d[j][i]+t; } if(d[i][0]!=-1)ans=min(ans,d[i][0]); } for(int i=1;i<=n;i++) if(d[i][0]==ans)b[++b[0]]=i; return ans; } int main() { scanf("%d",&n); printf("%d\n",work(n)); for(int j=1;j<=b[0];j++) printf("%d ",b[j]); return 0; } |
Subscribe
计数器 9301023
OI 课件=>
OI 课件=>