题目链接:https://nanti.jisuanke.com/t/41349

题意:有一个灭火英雄,和一个灭火团队,一个人与一个团队比较。

灭火英雄到其他灭火点的最短路最大值,与一个团队到其他灭火点的最短路的最大距离*C,进行比较。

如果一个团队的一个人在k点,那么k点的最短路就是0,这样,我们可以构建一个虚拟点“0”点,跑团队的最短路

可以让“0”点到其他团队队员点为0,到其他点为inf,然后跑一次最短路就可以了,下面的代码是比赛时候的,懒得改,直接很难看的写了。


 #include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <string>
using namespace std; typedef long long LL;
#define inf 1e9
#define rep(i,j,k) for(int i = (j); i <= (k); i++)
#define rep__(i,j,k) for(int i = (j); i < (k); i++)
#define per(i,j,k) for(int i = (j); i >= (k); i--)
#define per__(i,j,k) for(int i = (j); i > (k); i--) const int N = ;
bool vis[N];
int mp[N][N];
bool fired[N];
int team[N];
int dis[N];
int V,E,S,K,C; int dijkstra(int s){ rep(i,,V) vis[i] = false; if(s){
rep(i,,V) dis[i] = inf;
rep(i,,V) dis[i] = mp[s][i];
vis[s] = true; rep(i,,V){//团队的 int x = -;
int c = inf; rep(j,,V){ if(!vis[j] && c > dis[j]) x = j, c = dis[j];
}
if(x == -) continue; vis[x] = true;
rep(p,,V){
if(!vis[p] && dis[x] + mp[x][p] < dis[p]){
dis[p] = dis[x] + mp[x][p];
}
} }
}
else{//英雄的
rep(i,,V) dis[i] = inf;
rep(i,,K) dis[team[i]] = ;
vis[s] = true; rep(i,,V){ int x = -;
int c = inf; rep(j,,V){ if(!vis[j] && c > dis[j]) x = j, c = dis[j];
}
if(x == -) continue; vis[x] = true;
rep(p,,V){
if(!vis[p] && dis[x] + mp[x][p] < dis[p]){
dis[p] = dis[x] + mp[x][p];
}
} }
} int ans = ;
rep(i,,V){ if(dis[i] == inf) continue;
if(fired[i]) ans = max(ans,dis[i]);
} return ans;
} int main(){ ios::sync_with_stdio(false);
cin.tie(); int T;
cin >> T; int p = ;
int q = ;
while(T--){
cin >> V >> E >> S >> K >> C; rep(i,,V) rep(j,,V){
if(i == j) mp[i][j] = ;
else mp[i][j] = inf;
} rep(i,,K){
cin >> team[i];
} int u,v,w; rep(i,,E){
cin >> u >> v >> w;
fired[v] = true;
if(mp[u][v] > w){
mp[u][v] = mp[v][u] = w;
}
} p = dijkstra(S);//英雄 q = dijkstra();//团队 if(p <= q*C) cout << p << endl;
else cout << q << endl;
} getchar();getchar(); return ;
}

最新文章

  1. ReactiveCocoa代码实践之-更多思考
  2. Win10 for Phone 裁剪控件
  3. 翻译-In-Stream Big Data Processing 流式大数据处理
  4. POJ3414Pots
  5. AngularJS 学习笔记二
  6. WebView相关设置
  7. phpcms v9后台美化需要修改的部分整理
  8. cgdb调试postgresql
  9. 深度围观block:第三集
  10. 13年山东省赛 The number of steps(概率dp水题)
  11. 深入浅出Java动态代理
  12. java.lang.Exception: 资源处理失败,失败原因:com.mysql.jdbc.exceptions.jdbc4.MySQLSyntaxErrorException: Unknown column &#39;?????‰&#39; in &#39;where clause&#39;
  13. laravel整合JWT遇到的问题及解决方案
  14. SpringBoot自动装配源码解析
  15. [RESTful] DHC Client
  16. centos7下安装docker(26如何配置Health Check)
  17. OneinStack——PHP多版本共存
  18. Angular 学习笔记 (Material Select and AutoComplete)
  19. [20171130]关于rman备份疑问.txt
  20. Android:真机调试遇到的问题(INSTALL_FAILED_CANCELLED_BY_USER和INSTALL_FAILED_INSUFFICIENT_STORAGE)

热门文章

  1. clickhouse 离线/在线 安装和java通过jdbc链接
  2. [LeetCode] 9. Palindrome Number 验证回文数字
  3. python总结十
  4. Nacos配置的多环境管理
  5. 释放mac磁盘空间
  6. Unity Shader 屏幕后效果——Bloom外发光
  7. TCP连接的建立(三次握手和四次挥手)
  8. Vue双向绑定原理(我尽量写的。简洁)
  9. IDEA整合GIT所有操作
  10. 使用SonarQube和SonarQube Scanner分析项目