题解 P5754 【[NOI1997]最优乘车】
Warriors_Cat
·
·
题解
又来码题解咯~~
其实只是为了补一下咕值QAQ
首先，看到这一道题，我第一步想到的就是最短路。
为什么？蒟蒻的灵魂拷问QAQ
因为这道题在一定程度上是可以把公交车信息转化成一个图，而最少转车次数就是它的最短路。
所以，我们可以预处理出这样的一个图，然后就用堆优化dijkstra模板跑一遍最短路就可以了。
那么，我们怎么建图呢？
首先，在一条信息之内，每两个公交车站可以互相到达，不需要换车，于是这两个公车站之间的权值为0；
其次，对于同一个车站，我们可以枚举出两条信息都有没有包含这一个车站。如果有，就在它们之间连一条权值为1的边。
于是，建图就这样大功告成了！0^_^0
```cpp
void Add_nei(){
for(int k = 1; k <= m; ++k){
for(int i = 1; i < mp[k][0]; ++i){
for(int j = i + 1; j <= mp[k][0]; ++j){
int x, y, z, w;
x = z = k;
y = mp[k][i], w = mp[k][j];
add(x * 1000 + y, z * 1000 + w, 0);//相同信息内两个车站的连边
}
}
}
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
if(vis[j][i]){
int x, y, z, w;
x = j, y = i, w = i;
for(int k = 1; k <= m; ++k){
if(k == j) continue;
if(vis[k][i]){
z = k;
add(x * 1000 + y, z * 1000 + w, 1);//相同车站的连边
}
}
}
}
}
return;
}
```
当然，这道题还有许多需要处理的地方：
$i.$输入。这里是以换行符为分界点来输入的。大家可以用手写快读来处理输入，我用的是$string$的$getline$输入。
$ii.$节点表示。因为这里涉及到公交车信息，所以我们需要同时存储信息编号和公交车站编号。但，为了前向星链表的存储，我是用的是哈希，节约空间。
$iii.$最后输出。注意输出时应当每个信息里的$n$号车站的最小值。
于是，这道题就这么结束了……
接下来上完整$Code$啦~~
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cctype>
#include <string>
using namespace std;
int m, n, mp[110][510], ans = 0x7fffffff;
bool vis[110][510];
string s;
struct edge{
int v, w, nxt;
}e[2500010];
int head[2500010], cnt, dis[2500010];
inline void add(int u, int v, int w){//前向星
e[++cnt].v = v;
e[cnt].w = w;
e[cnt].nxt = head[u];
head[u] = cnt;
}
void work(int k){//输入处理
int sz = s.size();
for(int i = 0; i < sz; ++i){
int x = 0;
while(s[i] >= '0' && s[i] <= '9'){
x = (x << 3) + (x << 1) + (s[i] ^ 48);
++i;
}
mp[k][++mp[k][0]] = x;
vis[k][x] = 1;
}
return;
}
void Add_nei(){//建图
for(int k = 1; k <= m; ++k){
for(int i = 1; i < mp[k][0]; ++i){
for(int j = i + 1; j <= mp[k][0]; ++j){
int x, y, z, w;
x = z = k;
y = mp[k][i], w = mp[k][j];
add(x * 1000 + y, z * 1000 + w, 0);//相同信息内两个车站的连边
}
}
}
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
if(vis[j][i]){
int x, y, z, w;
x = j, y = i, w = i;
for(int k = 1; k <= m; ++k){
if(k == j) continue;
if(vis[k][i]){
z = k;
add(x * 1000 + y, z * 1000 + w, 1);//相同车站的连边
}
}
}
}
}
return;
}
struct node{
int u, d;
bool operator<(const node&rhs)const{
return d > rhs.d;
}
};
priority_queue <node> q;
void Dij(){//dijkstra模板
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
dis[j * 1000 + i] = 0x3f3f3f3f;
}
}//最小值初始化最大
for(int i = 1; i <= m; ++i) dis[i * 1000 + 1] = 0;//车站1为0
for(int i = 1; i <= m; ++i) if(vis[i][1]) q.push((node){i * 1000 + 1, 0});
while(!q.empty()){
node data = q.top();
q.pop();
int u = data.u, d = data.d;
if(d != dis[u]) continue;
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].v, w = e[i].w;
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
q.push((node){v, dis[v]});
}
}
}
return;
}
int main(){
scanf("%d%d", &m, &n);
getline(cin, s);
for(int i = 1; i <= m; ++i){
getline(cin, s);
work(i);
}
Add_nei();
Dij();
for(int i = 1; i <= m; ++i) ans = min(ans, dis[i * 1000 + n]);//取最小值
if(ans == 0x3f3f3f3f){//注意特判
printf("NO");
return 0;
}
printf("%d", ans);
return 0;
}
```
这篇题解就到此结束了，求大家的资瓷QAQ
~~帮忙点个赞呗~~
## End