admin管理员组文章数量:1577819
1003 Emergency (25 point(s))
As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.
Example:
#include<iostream>
#include<vector>
#include<list>
using namespace std;
typedef int Vertex;
struct Link {
Vertex vertex;
int dist;
};
struct Graph {
int Nv;
int Ne;
vector<list<Link>> Adj;
vector<Vertex> Team;
};
struct PathType {
int dist;
int team;
} Path;
int Count, Dist, Teams;
void DFS(Graph &G, Vertex v, Vertex c, vector<bool> &Visited)
{
if(v == c) {
Path.team += G.Team[c];
if(Dist == -1 || Path.dist < Dist) {
Dist = Path.dist;
Count = 1;
Teams = Path.team;
} else if(Path.dist == Dist) {
Count++;
if(Teams < Path.team)
Teams = Path.team;
}
Path.team -= G.Team[c];
} else {
if(Visited[v]) return ;
Visited[v] = true;
Path.team += G.Team[v];
for(auto &x : G.Adj[v]) {
if(!Visited[x.vertex]) {
Path.dist += x.dist;
DFS(G, x.vertex, c, Visited);
Path.dist -= x.dist;
}
}
Visited[v] = false;
Path.team -= G.Team[v];
}
}
void ShortestPath(Graph &G, Vertex v, Vertex c)
{
vector<bool> Visited(G.Nv, false);
Count = 0;
Teams = 0;
Dist = -1;
Path.team = 0;
Path.dist = 0;
DFS(G, v, c, Visited);
cout << Count << ' ' << Teams << endl;
}
int main()
{
int N, M, C1, C2;
cin >> N >> M >> C1 >> C2;
Graph G;
G.Nv = N;
G.Ne = M;
G.Adj.resize(N);
G.Team.resize(N);
for(int i = 0; i < N; i++){
cin >> G.Team[i];
}
for(int i = 0; i < M; i++){
int c1, c2, dist;
cin >> c1 >> c2 >> dist;
G.Adj[c1].push_back({c2, dist});
G.Adj[c2].push_back({c1, dist});
}
ShortestPath(G, C1, C2);
}
思路:
查找图的最短路径,利用DFS,然后记录下最短路径下支持的最大救援队伍数量。
版权声明:本文标题:1003 Emergency (25 point(s)) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dongtai/1727823457a1131997.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论