#include<iostream>
#define INF 1000000
using namespace std;
struct tra{
    int s;
    int dist;
};
tra car[5];
int ans=INF;
int n,dist[101][101];
void dfs(int s){
    int i; 
    if(s==n){
        ans=min(ans,car[1].dist+car[2].dist+car[3].dist);
        return;
    }
    else{
        for(i=1;i<=3;i++){
            car[i].dist+=dist[car[i].s][s+1];
            int t=car[i].s;
            car[i].s=s+1;
            dfs(s+1);
            car[i].s=t;
            car[i].dist-=dist[car[i].s][s+1];
        }
    }
    
}
int main(){
    int i,j;
    cin>>n;
    for(i=1;i<=n-1;i++){
        for(j=i+1;j<=n;j++){
            cin>>dist[i][j];
        }
    }
    for(i=1;i<=3;i++){
        car[i].dist=0;
        car[i].s=1;
    }
    dfs(1);
    cout<<ans;
    return 0;
}

dp可过：先跑floyed，求出两点之间的最短距离，然后通过dp[i][j][k]值向后更新（i>j>k）,即可。

#include <iostream>
#include <cstdio>
using namespace std;
const int mod=2333333;
int head[mod+10],to[mod+10],next[mod+10],tot;
void add(int a)
{
    to[++tot]=a;
    next[tot]=head[a%mod];
    head[a%mod]=tot;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int x;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        add(x);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&x);
        bool flag=false;
        for(int j=head[x%mod];j;j=next[j])
        {
            if(to[j]==x)
            {
                flag=true;
                printf("YES\n");
                break;
            }
        }
        if(flag==false) printf("NO\n");
    }
}

/*思路：dp

dp[i][j][k]表示第一辆车在第i个城市，第二辆车在第j个城市，第三辆车在第k个城市的最小路径；

初始化:f[1][1][1]=0,其余为Max
now表示当前到达的最远的城市(即now=max(i,j,k))
f[now+1][j][k]=min(f[now+1][j][k],f[i][j][k]+a[i][now+1])
f[i][now+1][k]=min(f[i][now+1][k],f[i][j][k]+a[j][now+1])
f[i][j][now+1]=min(f[i][j][now+1],f[i][j][k]+a[k][now+1])
在所有的now=n时，记录最小值。*/

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<stdlib.h>
5 #include<string.h>
6 #include<math.h>
7 #include<queue>
8 using namespace std;
9 typedef long long LL;
10 int dp[105][105][105];
11 int nn[200][200];
12 const int N=1e9;
13 int main(void)
14 {
15 int i,j,k;
16 while(scanf("%d",&k)!=EOF)
17 {
18 int x,y;
19 for(i=1; i<k; i++)
20 {
21 for(j=i+1;j<=k;j++)
22 {
23 scanf("%d",&nn[i][j]);
24 }
25 }
26 for(i=0; i<105; i++)
27 {
28 for(j=0; j<105; j++)
29 {
30 for(x=0; x<105; x++)
31 {
32 dp[i][j][x]=N;
33 }
34 }
35 }
36 int ans=1e9;
37 dp[1][1][1]=0;
38 for(i=1; i<k; i++)
39 {
40 for(j=1; j<k; j++)
41 {
42 for(x=1; x<k; x++)
43 {
44 int xx=max(i,j);
45 xx=max(x,xx);
46 dp[xx+1][j][x]=min(dp[xx+1][j][x],dp[i][j][x]+nn[i][xx+1]);
47 dp[i][xx+1][x]=min(dp[i][xx+1][x],dp[i][j][x]+nn[j][xx+1]);
48 dp[i][j][xx+1]=min(dp[i][j][xx+1],dp[i][j][x]+nn[x][xx+1]);
49 if(xx+1==k)
50 {ans=min(dp[xx+1][j][x],ans);
51 ans=min(dp[i][j][xx+1],ans);
52 ans=min(ans,dp[i][xx+1][x]);
53 }
54 }
55 }
56 }
57 printf("%d\n",ans);
58 }
59 return 0;
60 }

这题数据太弱，正解应该是三维的记忆搜索。很多人的贪心都是错的
如：
input：
6
1 2 1 1 10000
10 10000 10000 10000
10000 100 10000
100 10000
1

output
14

输出105的都是贪心，是错误的。答案应该是14。
var a:array[0..100,0..100] of longint;
b:array[1..100,1..100,1..100] of longint;
n,m,i,j,k,l:longint;

function minn(x,y:longint):longint;
begin
if x=0 then exit(y);
if y=0 then exit(x);
if x<y then exit(x)
else exit(y);
end;
function pan(x,y,z:longint):boolean;
begin
pan:=false;
if x>=z-1 then exit(true);
if y>=z-1 then exit(true);
end;
begin
read(n);
for i:=1 to n do
for j:=i+1 to n do
begin
read(a[i,j]);
a[j,i]:=a[i,j];
end;
for i:=1 to n do
for j:=1 to n do
for k:=1 to n do
begin
if k>1 then
begin
b[i,j,k]:=minn(b[i,j,k],b[i,j,k-1]+a[k-1,k]);
if pan(i,j,k) then
for l:=1 to k-1 do
b[i,j,k]:=minn(b[i,j,k],b[i,j,l]+a[l,k]);
end;

if j>1 then
begin
b[i,j,k]:=minn(b[i,j,k],b[i,j-1,k]+a[j-1,j]);
if pan(i,k,j) then
for l:=1 to j-1 do
b[i,j,k]:=minn(b[i,j,k],b[i,l,k]+a[l,j]);
end;

if i>1 then
begin
b[i,j,k]:=minn(b[i,j,k],b[i-1,j,k]+a[i-1,i]);
if pan(k,j,i) then
for l:=1 to i-1 do
b[i,j,k]:=minn(b[i,j,k],b[l,j,k]+a[l,i]);
end;
end;

for i:=1 to n do
for j:=1 to n do
m:=minn(m,b[i,j,n]);
for i:=1 to n do
for k:=1 to n do
m:=minn(m,b[i,n,k]);
for j:=1 to n do
for k:=1 to n do
m:=minn(m,b[n,j,k]);
writeln(m);
end.

dfs
cur表示目前到达的最远的城市，car1表示第一辆车到达的城市，car2，car3以此类推，dist为目前的距离

#include<bits/stdc++.h>
using namespace std;
int n,a[110][110],ans=1e9;
void dfs(int cur,int car1,int car2,int car3,int dist){
    if(cur==n){
        ans=min(ans,dist);
        return;
    }
    dfs(cur+1,cur+1,car2,car3,dist+a[car1][cur+1]);
    dfs(cur+1,car1,cur+1,car3,dist+a[car2][cur+1]);
    dfs(cur+1,car1,car2,cur+1,dist+a[car3][cur+1]);
    return;
}
int main(){
    scanf("%d",&n); 
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            scanf("%d",&a[i][j]);   
        }
    }
    dfs(1,1,1,1,0);
    printf("%d\n",ans);
    return 0;
}

题意不明，只需要一辆车到终点即可，测试数据都看了半天
#include <cstdio>
int max(int a,int b){
return a>b?a:b;
}
int n,map[110][110];
int ans=99999999;
void dfs(int dist,int city,int c1,int c2,int c3){
if(c1==n||c2==n||c3==n){
ans=ans<dist?ans:dist;
return;
}
for(int i=c1+1;i<=city;i++)
dfs(dist+map[c1][i],city,i,c2,c3);
dfs(dist+map[c1][city+1],city+1,city+1,c2,c3);

for(int i=c2+1;i<=city;i++)
dfs(dist+map[c2][i],city,c1,i,c3);
dfs(dist+map[c2][city+1],city+1,c1,city+1,c3);

for(int i=c3+1;i<=city;i++)
dfs(dist+map[c3][i],city,c1,c2,i);
dfs(dist+map[c3][city+1],city+1,c1,c2,city+1);
}

int main(){
freopen("QQQ.txt","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n-i;j++){
int x;
scanf("%d",&x);
map[i][i+j]=map[i+j][i]=x;
}

dfs(0,1,1,1,1);
printf("%d",ans);
return 0;
}

int mymin(int x,int y){return x??y?x:y;}

void dfs(int a,int b,int c,int s)
{
if(dp[a][b][c]<=s)return ;
dp[a][b][c]=s;
if(a==n)
{
ans=mymin(ans,s);
return ;
}
dfs(a+1,??,??,s+map[a][a+1]);
dfs(a+1,??,??,s+map[b][a+1]);
dfs(a+1,??,??,s+map[c][a+1]);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
scanf("%d",&map[i][j]);
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
dp[i][j][k]=最大;
ans=最大;
dfs(?,?,?,?);
printf("%d",ans);
}

我觉得无语的是，样例数据不能构成三角形，，，，，难道路不是直线是非常非常非常曲折的？

else begin a[a1,a2,a3]:=min(a[a1,a2,a3],b[a3-1,a3]+dfs(a1,a2,a3-1));未考虑。。。哎

发的正解
program p1547;
var a:array[0..101,0..101,0..101] of longint;
n,sum,i,j:longint;
b:array[0..101,0..101] of longint;
c:array[1..3] of longint;
//
function min(a,b:longint):longint;
begin
if a>b then exit(b)
else exit(a);
end;
//
procedure make(a1,a2,a3:longint;var b1,b2,b3:longint);
var k,i,j:longint;
begin
c[1]:=a1;c[2]:=a2;c[3]:=a3;
for i:=1 to 3 do
for j:=i+1 to 3 do
if c[i]>c[j] then
begin
k:=c[i];c[i]:=c[j];c[j]:=k;
end;
b1:=c[1];b2:=c[2];b3:=c[3];
end;
//
function dfs(a1,a2,a3:longint):longint;
var i,b1,b2,b3:longint;
begin
if a[a1,a2,a3]<>10000000 then exit(a[a1,a2,a3]);
if a2+1>=a3 then
for i:=1 to a3-1 do
begin
make(a1,a2,i,b1,b2,b3);
a[a1,a2,a3]:=min(a[a1,a2,a3],b[i,a3]+dfs(b1,b2,b3));
end
else begin
a[a1,a2,a3]:=min(a[a1,a2,a3],b[a3-1,a3]+dfs(a1,a2,a3-1));
end;
for i:=1 to a2-1 do
begin
make(a1,i,a3,b1,b2,b3);
a[a1,a2,a3]:=min(a[a1,a2,a3],b[i,a3]+dfs(b1,b2,b3));
end;
for i:=1 to a1-1 do
begin
make(i,a2,a3,b1,b2,b3);
a[a1,a2,a3]:=min(a[a1,a2,a3],b[i,a3]+dfs(b1,b2,b3));
end;
exit(a[a1,a2,a3]);
end;
//
procedure init;
var i,j,k:longint;
begin
readln(n);
for i:=1 to n-1 do
begin
for j:=i+1 to n do
begin
read(b[i,j]);b[j,i]:=b[i,j];
end;
readln;
end;
for i:=1 to n do
for j:=1 to n do
for k:=1 to n do a[i,j,k]:=10000000;
a[1,1,1]:=0;
end;
//
begin
init;
sum:=dfs(n,n,n);
sum:=10000000;
for i:=1 to n do
for j:=1 to n do sum:=min(sum,a[i,j,n]);
write(sum);
end.

有件事很恐怖——明知道自己是错的还AC了……
附错的代码：
uses math;
var
i,j,k,m,n,minx,minp,s:longint;
c:array[1..3] of longint;
a:array[1..100,1..100] of longint;

begin
readln(n); s:=0;
fillchar(a,sizeof(a),0);
for i:=1 to 3 do
c[i]:=1;
for i:=1 to n-1 do
begin
for j:=i+1 to n do
begin
read(a[i,j]);
a[j,i]:=a[i,j];
end;
readln
end;
for i:=2 to n do
begin
minp:=maxlongint;
for j:=1 to 3 do
if minp>a[i,c[j]] then
begin
minp:=a[i,c[j]];
minx:=j;
end;
s:=s+minp;
c[minx]:=i;
end;
writeln(s)
end.
贪心万岁！！！

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

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

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

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

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

Accepted / 100 / 1024ms / 448KB

好吧我没用递归

兄弟们,动规没有饭吃,用摸拟!!!!!!!!!!

Var

i,j,k,m,n,t:longint;

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

xx:array[1..3,1..2]of longint;

Begin

readln(n);

for i:=1 to n-1 do

begin

for j:=i+1 to n do

read(qw);

readln;

end;

for i:=1 to 3 do

begin

xx:=1;

xx:=0;

end;

for i:=2 to n do

begin

m:=maxlongint;

for j:=1 to 3 do

begin

if xx[j,2]+qw[xx[j,1],i]

不错的题。

给个伪码：

now：A、B、C所到达的序号最大的城市

（我的城市编号是从0，1，2...n-1）

a：A车的位置

b：B车的位置

c：C车的位置

d[i][j]：城i和城j的距离

ans：最佳答案，初始化为一个很大的值

s：A、B、C车处于(a,b,c)时的最小路程

#include "stdio.h"

int ans

每一点可以拓展最多3次,

记录该点第I时刻所有的车数即可拓展的点.

于是只要2维. 每次都走能拓展的最短的路

奇迹般1次AC...O(n^3)的顺推法

输入上纠结了很久

最后敲定for i:=1 to n-1 do

for j:=i+1 to n do

我貌似也是贪心..

冲着这70%的通过率进来的..和题目的通过率比起来..本人的通过率是多么可怜..

OTZ 逆转裁判的标题

果然强大..

...70%的通过率