PYA A_1003 Emergency
本帖最后由 798236606 于 2020-2-22 15:53 编辑传送门：https://pintia.cn/problem-sets/994805342720868352/problems/994805523835109376
解：
最短路径
1.迪杰斯特拉
#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;
const int maxn = 510;
int n, m, c1, c2;
int G;
int men;//存放点权，即救援队数
int num;//存放到每个点的最短路径数
int w;//存放可聚集的队伍数
int v;//存放最短路径长度
bool vis;//是否访问过
void DJS(int s)
{
fill(v, v + n, INT_MAX);
fill(num, num + n, 0);
fill(w , w + n, 0);
v = 0;
w = men;
num = 1;
for (int i = 0; i < n; i++)
{
int u = -1, min = INT_MAX;
for (int i = 0; i < n; i++)//查找未被访问过且距离最短的顶点
if (!vis && v < min)min = v;
if (u == -1) return;//如果剩下的顶点与源点不通，返回
vis = true;
for (int j = 0; j < n; j++)
{
if (vis || G == INT_MAX) continue;
int t = v + G;
if (t < v)
{
v = t;
num = num;
w = w + men;
}
else if (t == v)
{
num += num;
if (w + men > w) w = w + men;
}
}
}
}
int main(void)
{
scanf("%d %d %d %d", &n, &m, &c1, &c2);
fill(G, G + maxn * maxn, INT_MAX);
for (int i = 0; i < n; i++)
scanf("%d", men + i);
while (m--)
{
int a, b, l;
scanf("%d %d %d", &a, &b, &l);
G = G = l;
}
DJS(c1);
printf("%d %d", num, w);
return 0;
}
2.迪杰斯特拉 + DFS （模板）
#include <cstdio>
#include <climits>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 510;
int n, m, c1, c2;
int G;
int weight;//存放点权，即救援队数
int d;//存放最短路径长度
bool vis;//是否访问过
vector<int> pre;//存放顶点在最短路径中的前驱
void DJS(int s)
{
fill(d, d + n, INT_MAX);
d = 0;
for (int i = 0; i < n; i++)
{
int u = -1, min = INT_MAX;
for (int i = 0; i < n; i++)//查找未被访问过且距离最短的顶点
if (!vis && d < min)min = d;
if (u == -1) return;//如果剩下的顶点与源点不通，返回
vis = true;
for (int v = 0; v < n; v++)
{
if (vis || G == INT_MAX) continue;
int t = d + G;
if (t < d)
{
d = t;
pre.clear();
pre.push_back(u);
}
else if (t == d)
pre.push_back(u);
}
}
}
int num = 0;//存放最短路径条数
int opt_w = 0;//存放最大点权和
vector<int> path;
void DFS(int v)
{
if (v == c1)//递归边界，如果遍历到起点
{
path.push_back(v);
num++;
int val = 0;
for (int i = path.size() - 1; i >= 0; i--)
val += weight];
if (val > opt_w) opt_w = val;
path.pop_back();
return;
}
path.push_back(v);
for (int i = 0; i < pre.size(); i++)
DFS(pre);
path.pop_back();
}
int main(void)
{
scanf("%d %d %d %d", &n, &m, &c1, &c2);
fill(G, G + maxn * maxn, INT_MAX);
for (int i = 0; i < n; i++)
scanf("%d", weight + i);
while (m--)
{
int a, b, l;
scanf("%d %d %d", &a, &b, &l);
G = G = l;
}
DJS(c1);
DFS(c2);
printf("%d %d", num, opt_w);
return 0;
}
3.BF算法
#include <cstdio>
#include <climits>
#include <cstring>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
const int maxn = 510;
typedef struct node{
int id, dis;
node (int _id, int _dis) : id(_id), dis(_dis) {};
}Node;
int n, m, c1, c2;
int weight;//存放点权，即救援队数
int num;//存放到每个点的最短路径数
int w;//存放可聚集的队伍数
int d;//存放最短路径长度
vector<Node> adj;//邻接表
set<int> pre;//存放顶点在最短路径中的前驱
void BF(int s)
{
fill(d, d + n, INT_MAX);
memset(w, 0, sizeof(w));
memset(num, 0, sizeof(num));
w = weight;
d = 0;
num = 1;
for (int i = 0; i < n - 1; i++)
{
for (int u = 0; u < n; u++)
{
if (d == INT_MAX) continue;
for (int v = 0; v < adj.size(); v++)
{
int id = adj.id, dis = adj.dis;
if (dis + d < d)
{
d = dis + d;
num = num;
w = weight + w;
pre.clear();
pre.insert(u);
}
else if (dis + d == d)
{
if (weight + w > w)
w = weight + w;
num = 0;
pre.insert(u);
for (set<int>::iterator it = pre.begin(); it != pre.end(); ++it)
num += num[*it];
}
}
}
}
}
int main(void)
{
// freopen("input.txt", "r", stdin);
scanf("%d %d %d %d", &n, &m, &c1, &c2);
for (int i = 0; i < n; i++)
scanf("%d", weight + i);
while (m--)
{
int a, b, l;
scanf("%d %d %d", &a, &b, &l);
adj.push_back(node(b, l));
adj.push_back(node(a, l));
}
BF(c1);
printf("%d %d", num, w);
return 0;
}
页:
[1]