描述
题解
好长的英文题,看得我都心碎了~~~
百度了一下大意:
三个数字n、c、r,n代表城市的个数,c代表损坏的车辆的数量,r代表有几条路,然后接下去有c+1个字符串,第一个代表拖车公司的所在地,后面的c个地点表示损坏的需要拖回来的车辆所在地。在接下去r个字符串,代表r条路,左右为两个城市名,中间的一串字符中,只含有<-代表该条路是从右边的城市通向左边的,以此类推,而数字代表该条路的长度,求把所有车一一拖回来所需经过的总路程。
这道题用的数据结构是<map
>,算法可以用一遍Floyd或者两遍Dij,前者比较容易写,后者稍微麻烦一些,因为需要反向建图。
这里有不少坑,如果英语不好的话,最大的坑便是,一个城市可以有多辆抛锚的车,但是你每次只能拉回一个……坑死我了,找了好久bug~~~
代码
#include <iostream>
#include <map>
#include <string>
#include <cstring>
using namespace std;
map<string, int> m;
string s;
/* * 单源最短路径,Dijkstra算法,邻接矩阵形式,复杂度为O(n^2) * 求出源beg到所有点的最短路径,传入图的顶点数和邻接矩阵cost[][] * 返回各点的最短路径lowcost[],路径pre[],pre[i]记录beg到i路径上的父节点,pre[beg] = -1 * 可更改路径权类型,但是权值必须为非负,下标0~n-1 */
const int MAXN = 101;
const int INF = 0x3f3f3f3f; // 表示无穷
bool vis[MAXN];
int pre[MAXN];
int cost[MAXN][MAXN];
int cost_[MAXN][MAXN];
int lowcost[MAXN];
int lowcost_[MAXN];
void Dijkstra(int cost[][MAXN], int lowcost[], int n, int beg)
{
for (int i = 0; i < n; i++)
{
lowcost[i] = INF;
vis[i] = false;
pre[i] = -1;
}
lowcost[beg] = 0;
for (int j = 0; j < n; j++)
{
int k = -1;
int min = INF;
for (int i = 0; i < n; i++)
{
if (!vis[i] && lowcost[i] < min)
{
min = lowcost[i];
k = i;
}
}
if (k == -1)
{
break;
}
vis[k] = true;
for (int i = 0; i < n; i++)
{
if (!vis[i] && lowcost[k] + cost[k][i] < lowcost[i])
{
lowcost[i] = lowcost[k] + cost[k][i];
pre[i] = k;
}
}
}
}
int cars[MAXN];
int main(int argc, const char * argv[])
{
int N, C, R;
int key = 1;
while (cin >> N >> C >> R, N + C + R != 0)
{
m.clear();
memset(cars, 0, sizeof(cars));
cin >> s;
m[s] = 1; // 拖车所在地表示为1
int pos = 2;
for (int i = 0; i < C; i++)
{
cin >> s;
if (m[s] == 0)
{
m[s] = pos++;
}
cars[m[s] - 1]++;
}
int tag = pos - 1;
memset(cost, 0x3f, sizeof(cost));
memset(cost_, 0x3f, sizeof(cost_));
int num;
char a, b, c, d;
string st, ed;
for (int i = 0; i < R; i++)
{
cin >> st >> a >> b >> num >> c >> d >> ed;
if (m[st] == 0)
{
m[st] = pos++;
}
if (m[ed] == 0)
{
m[ed] = pos++;
}
int u = m[st] - 1;
int v = m[ed] - 1;
if (a == '<')
{
if (cost[v][u] > num)
{
cost[v][u] = num;
}
if (cost_[u][v] > num)
{
cost_[u][v] = num;
}
}
if (d == '>')
{
if (cost[u][v] > num)
{
cost[u][v] = num;
}
if (cost_[v][u] > num)
{
cost_[v][u] = num;
}
}
}
Dijkstra(cost, lowcost, pos - 1, 0);
Dijkstra(cost_, lowcost_, pos - 1, 0);
int sum = 0;
for (int i = 1; i < tag; i++)
{
sum += (lowcost[i] + lowcost_[i]) * cars[i];
}
printf("%d. %d\n", key++, sum);
}
return 0;
}