题目描述
【题目背景】
公元215年，刘备取益州，孙权令诸葛瑾找刘备索要荆州。刘备不答应，孙权极为恼恨，便派吕蒙率军取长沙、零陵、桂阳三郡。长沙、桂阳蜀将当即投降。刘备得知后，亲自从成都赶到公安(今湖北公安)，派大将关羽争夺三郡。孙权也随即进驻陆口，派鲁肃屯兵益阳，抵挡关羽。双方剑拔弩张，孙刘联盟面临破裂，在这紧要关头，鲁肃为了维护孙刘联盟，不给曹操可乘之机，决定当面和关羽商谈。“肃邀羽相见，各驻兵马百步上，但诸将军单刀俱会”。双方经过会谈，缓和了紧张局势。随后，孙权与刘备商定平分荆州，“割湘水为界，于是罢军”，孙刘联盟因此能继续维持。
【问题描述】
关羽受鲁肃邀请，为了大局，他决定冒险赴会。他带着侍从周仓，义子关平，骑着赤兔马，手持青龙偃月刀，从军营出发了，这就是历史上赫赫有名的“单刀赴会”。关羽平时因为军务繁重，决定在这次出行中拜访几个多日不见的好朋友。然而局势紧张，这次出行要在限定时间内完成，关公希望你能够帮助他安排一下行程，安排一种出行方式，使得从军营出发，到达鲁肃处赴会再回来，同时拜访到尽可能多的朋友，在满足这些条件下行程最短。注意拜访朋友可以在赴会之前，也可以在赴会之后。现在给出地图，请你完成接下来的任务。
输入
第一行
n
,
m
,
k
,
t
n,m,k,t
n,m,k,t，代表有
n
n
n个地点，
m
m
m条道路,有
k
k
k个朋友(不包括鲁肃)，以及限定时间
t
t
t(行走
1
1
1单位长度的路程用时
1
1
1单位时间)。 接下来m行，每行有
x
,
y
,
w
x,y,w
x,y,w三个整数，代表
x
x
x和
y
y
y之间有长度为
w
w
w的道路相连。 接下来一行有
k
k
k个整数，代表朋友所在的都城编号(保证两两不同，且不在
1
1
1和
n
n
n) （我们约定1是关羽的营地，n是鲁肃的营地）
输出
输出两个整数，分别是最多可以拜访的朋友数，以及在这种情况下最少需要耗费的时间，如果连到达鲁肃再回来都无法完成，输出一个
−
1
-1
−1就可以了。
样例输入
5
5
5
7
7
7
2
2
2
15
15
15
1
1
1
2
2
2
5
5
5
1
1
1
3
3
3
3
3
3
2
2
2
3
3
3
1
1
1
2
2
2
4
4
4
1
1
1
3
3
3
4
4
4
4
4
4
2
2
2
5
5
5
2
2
2
4
4
4
5
5
5
3
3
3
2
2
2
4
4
4
样例输出
2
2
2
14
14
14
提示
【数据规模和约定】 有
10
10
10%数据，
n
≤
10
,
m
≤
50
,
k
≤
5
n≤10,m≤50,k≤5
n≤10,m≤50,k≤5; 有
10
10
10%数据，
k
=
0
k=0
k=0; 有
10
10
10%数据，
k
=
1
k=1
k=1; 另
30
30
30%数据，
k
≤
5
k≤5
k≤5; 对于
100
100
100%数据，
n
≤
10000
,
m
≤
50000
,
k
≤
15
,
t
≤
2147483647
,
w
≤
10000
n≤10000,m≤50000,k≤15,t≤2147483647,w≤10000
n≤10000,m≤50000,k≤15,t≤2147483647,w≤10000
解析
首先，我们会发现其实有用点只有
k
k
k个朋友与起点、终点共
k
+
2
k+2
k+2个点。 而
k
≤
15
k≤15
k≤15，因此数据范围急剧下降。 因为要求最短路，我们可以先对这些点以各点为源点做
k
+
2
k + 2
k+2次单源最短路，统计出这些有用点之间的最短路 之后考虑状压（
k
k
k那么小，不状压还能咋做？）
f
[
s
t
a
]
[
i
]
f[sta][i]
f[sta][i]表示已经走过的点的集合为
s
t
a
sta
sta，当前在
i
i
i的最少时间
f
[
s
t
a
]
[
i
]
=
m
i
n
(
f
[
s
t
a
′
]
[
j
]
+
d
i
s
(
i
,
j
)
)
(
j
∈
s
t
a
′
,
s
t
a
′
⊂
s
t
a
,
s
t
a
−
s
t
a
′
=
f[sta][i] = min(f[sta'][j] + dis(i , j))(j∈sta',sta'⊂sta,sta - sta' =
f[sta][i]=min(f[sta′][j]+dis(i,j))(j∈sta′,sta′⊂sta,sta−sta′= {
i
i
i }
)
)
)
最后统计答案时，优先保证状态合法（时间要
≤
t
≤t
≤t）且
1
1
1的个数尽量多，再考虑路径最短。 注意：DP出来的结果是不回到起点的，最终统计时要对
f
[
s
t
a
]
[
i
]
+
d
i
s
(
i
,
1
)
f[sta][i] + dis(i , 1)
f[sta][i]+dis(i,1)取
m
i
n
min
min
代码
#include<queue>
#include<stdio.h>
#include<cstring>
#define mp(x , y) make_pair(x , y)
using namespace std
;
const int maxk
= 20;
const int maxn
= 10005;
const int maxe
= 50005;
const int oo
= 1000000000;
priority_queue
< pair
< int , int > , vector
< pair
< int , int > > , greater
< pair
< int , int > > > Heap
;
int d
[maxn
];
int n
;
int edgenum
;
int Next
[maxe
<< 1] , vet
[maxe
<< 1] , val
[maxe
<< 1] , head
[maxn
];
int a
[maxk
] , D
[maxk
][maxk
];
int f
[1 << maxk
][maxk
] , one_num
[1 << maxk
];
int min(int x
, int y
){return x
< y
? x
: y
;}
void add_edge(int u
, int v
, int cost
)
{
edgenum
++;
Next
[edgenum
] = head
[u
];
vet
[edgenum
] = v
;
val
[edgenum
] = cost
;
head
[u
] = edgenum
;
}
void Dijkstra(int s
)
{
for(int i
= 1;i
<= n
;i
++) d
[i
] = oo
;
d
[s
] = 0;
Heap
.push(mp(d
[s
] , s
));
while(!Heap
.empty())
{
int u
= Heap
.top().second
, dis
= Heap
.top().first
;
Heap
.pop();
if(d
[u
] != dis
) continue;
for(int e
= head
[u
];e
;e
= Next
[e
])
{
int v
= vet
[e
];
if(d
[v
] > d
[u
] + val
[e
]) d
[v
] = d
[u
] + val
[e
] , Heap
.push(mp(d
[v
] , v
));
}
}
}
int main()
{
int m
, k
,t
;
scanf("%d%d%d%d",&n
,&m
,&k
,&t
);
while(m
--)
{
int u
, v
, cost
;
scanf("%d%d%d",&u
,&v
,&cost
);
add_edge(u
, v
, cost
);
add_edge(v
, u
, cost
);
}
Dijkstra(1);
if(d
[n
] + d
[n
] > t
)
{
puts("-1");
return 0;
}
a
[1] = 1;
for(int i
= 2;i
<= k
+ 1;i
++) scanf("%d",&a
[i
]);
a
[k
+ 2] = n
;
k
+= 2;
for(int i
= 1;i
<= k
;i
++)
{
Dijkstra(a
[i
]);
for(int j
= 1;j
<= k
;j
++) D
[i
][j
] = D
[j
][i
] = d
[a
[j
]];
}
memset(f
, 0x3f3f3f , sizeof f
);
f
[1][1] = 0;
for(int sta
= 2;sta
< (1 << k
);sta
++)
{
for(int i
= 1;i
<= k
;i
++)
{
if(!(sta
& (1 << i
- 1))) continue;
for(int j
= 1;j
<= k
;j
++)
{
if(!(sta
& (1 << j
- 1))) continue;
f
[sta
][i
] = min(f
[sta
][i
] , f
[sta
- (1 << i
- 1)][j
] + D
[i
][j
]);
}
}
}
one_num
[0] = 0;
for(int i
= 1;i
< (1 << k
);i
++) one_num
[i
] = one_num
[i
>> 1] + (i
& 1);
int cnt
= 2 , ans
= oo
;
for(int sta
= 0;sta
< (1 << k
);sta
++)
{
if(!(sta
& (1 << k
- 1)) || !(sta
& 1)) continue;
if(one_num
[sta
] < cnt
) continue;
int res
= oo
;
for(int i
= 1;i
<= k
;i
++)
{
if(!(sta
& (1 << i
- 1))) continue;
res
= min(res
, f
[sta
][i
] + D
[i
][1]);
}
if(res
> t
) continue;
if(one_num
[sta
] == cnt
) ans
= min(ans
, res
);
else if(one_num
[sta
] > cnt
) ans
= res
, cnt
= one_num
[sta
];
}
printf("%d %d\n",cnt
- 2 , ans
);
return 0;
}
