admin管理员组文章数量:1577814
题意:一张图,已知起点终点,计算起点到终点的所有最短路径,每个点上有一个数,代表这个点上的搜救队的数量,要求输出这些最短路径中你能召集到的最大的搜救队的数量。
方法一:dfs
#include <bits/stdc++.h>
using namespace std;
#define INF 0x7FFFFF
int n,m,st,en;
int map[501][501]={0};
int teams[501]={0};
int max_team=0,shortest_num=0,min_dis=INF;
bool visit[501]={0};
void dfs(int i,int dis,int team)//到达i结点时的距离(dis),team数
{
if(i==en)
{
if(dis<min_dis){
min_dis = dis;
shortest_num = 1;
max_team = team;
}
else if(dis == min_dis){
shortest_num++;
if(team>max_team){
max_team = team;
}
}
return;
}
visit[i]=1;
for(int j=0;j<n;j++)
{
if(visit[j]==0 && map[i][j]>0){
dfs(j,dis+map[i][j],team+teams[j]);
}
}
visit[i]=0;
}
int main()
{
cin>>n>>m>>st>>en;
for(int i=0;i<n;i++)
cin>>teams[i];
for(int i=0;i<m;i++){
int c1,c2,dis;
cin>>c1>>c2>>dis;
map[c1][c2]=map[c2][c1]=dis;
}
dfs(st,0,teams[st]);
cout<<shortest_num<<" "<<max_team<<endl;
return 0;
}
方法二:dijsktra
void dijkstra(int s)
{
amount[s]=teams[s];
path_count[s]=1;
dis[s]=0;
while(1)
{
int v = -1;
for(int i=0;i<n;i++){
if(!visit[i] && (v==-1 || dis[i]<dis[v]))
v=i;
}
if(v==-1) break;
visit[v]=1;
for(int i=0;i<n;i++){
if(visit[i]==0){
if(dis[i] > dis[v] + map[v][i]){
dis[i] = dis[v] + map[v][i];
amount[i] = amount[v] + teams[i];
path_count[i] = path_count[v];
}
else if(dis[i] == dis[v] + map[v][i]){
if( amount[i] < amount[v] + teams[i])
amount[i] = amount[v] + teams[i];
path_count[i] += path_count[v];
}
}
}
}
}
版权声明:本文标题:1003 Emergency(25 分)【dfsdijsktra】 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1727823271a1131976.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论