http://codeforces.com/gym/100625/attachments/download/3213/2013-benelux-algorithm-programming-contest-bapc-13-en.pdf

题意:给你一张无向图,t个可能的目的地,问在这t个点中哪些点的最短路中经过了g和h

思路:这是傻逼题,我直接dijstra用vector< set<int> > 保存路径, 最后再去判断下。。好像这并不是出题者想要的解法,不过时间还可以,300+ms

 #pragma comment(linker, "/STACK:1000000000")
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define LL long long
#define MAXN 100005
#define INF 0x3f3f3f3f
#define eps 1e-8
using namespace std;
struct Edge
{
int from, to, dist;
Edge(int from, int to, int dist):from(from), to(to), dist(dist){};
};
struct HeapNode
{
int d, u;
HeapNode(int d, int u):d(d), u(u){};
bool operator <(const HeapNode& rhs) const{
return d > rhs.d;
}
};
vector< set<int> > road[MAXN];
struct Dijstra
{
int n, m;
vector<Edge> edges;
vector<int> G[MAXN];
bool done[MAXN];
int d[MAXN];
int p[MAXN]; void init(int n){
this->n = n;
for(int i = ; i <= n; i++){
G[i].clear();
road[i].clear();
}
edges.clear();
} void AddEdge(int from, int to, int dist){
edges.push_back(Edge(from, to, dist));
m = edges.size();
G[from].push_back(m - );
} void dijstra(int s){
priority_queue<HeapNode> Q;
for(int i = ; i <= n; i++){
d[i] = INF;
}
d[s] = ;
memset(done, , sizeof(done));
Q.push(HeapNode(, s));
while(!Q.empty()){
HeapNode x = Q.top();
Q.pop();
int u = x.u;
if(done[u]) continue;
done[u] = true;
for(int i = ; i < G[u].size(); i++){
Edge& e = edges[G[u][i]];
if(d[e.to] > d[u] + e.dist){
d[e.to] = d[u] + e.dist;
road[e.to].clear();
if(road[u].empty()){
set<int> tmp;
tmp.clear();
tmp.insert(u);
road[e.to].push_back(tmp);
}
else{
for(int j = ; j < road[u].size(); j++){
road[e.to].push_back(road[u][j]);
road[e.to][j].insert(u);
}
}
p[e.to] = G[u][i];
Q.push(HeapNode(d[e.to], e.to));
}
else if(d[e.to] == d[u] + e.dist){
int w = road[e.to].size();
for(int j = ; j < road[u].size(); j++){
road[e.to].push_back(road[u][j]);
road[e.to][w + j].insert(u);
}
}
}
}
}
};
int n, m, t, g, h, s;
Dijstra p;
vector<int> res;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif // OPEN_FILE
int T;
scanf("%d", &T);
while(T--){
scanf("%d%d%d", &n, &m, &t);
scanf("%d%d%d", &s, &g, &h);
int x, y, z;
p.init(n);
for(int i = ; i <= m; i++){
scanf("%d%d%d", &x, &y, &z);
p.AddEdge(x, y, z);
p.AddEdge(y, x, z);
}
p.dijstra(s);
res.clear();
for(int i = ; i <= t; i++){
scanf("%d", &x);
for(int j = ; j < road[x].size(); j++){
road[x][j].insert(x);
if(road[x][j].find(g) != road[x][j].end() && road[x][j].find(h) != road[x][j].end()){
res.push_back(x);
break;
}
}
}
sort(res.begin(), res.end());
int w = res.size();
for(int i = ; i < w; i++){
printf("%d ", res[i]);
}
printf("\n");
}
}

最新文章

  1. C#程序以管理员身份运行
  2. android手机操作SD的使用方法
  3. SQL统计不重复字段的个数.
  4. Jam&#39;s math problem(思维)
  5. 每天进步一点点——再次了解Linux进程ID
  6. manifest中的largeHeap是干什么用的?
  7. virtualbox, vt-s, rmmod kvm-intel
  8. 前端模块化——seaJS
  9. linux文件截取前几行,后几行,中间几行命令
  10. 【MyBatis源码分析】Configuration加载(下篇)
  11. jvm 字节码执行 (二)动态类型支持与基于栈的字节码解释执行
  12. EffectiveC++ 第2章 构造/析构/赋值运算
  13. [转]TopShelf 用法
  14. $Django 模板层(模板导入,继承)、 单表*详(增删改查,基于双下划线的查询)、static之静态文件配置
  15. 数据结构 BM算法
  16. PowerBI发布到网页
  17. Consul之:服务注册与发现
  18. 02-OpenLDAP配置
  19. smali语法详解
  20. 【Redis】Redis学习(五) Redis cluster模式详解

热门文章

  1. ip iproute2的典型应用
  2. docker mysql 文件挂载和MySQL字符集设置
  3. Java (JDK7)中的String常量和String.intern的实现
  4. django admin显示多对多字段
  5. 模拟select样式,自定义下拉列表为树结构
  6. vue子组件使用指令 同时绑定v-model 指令没有作用
  7. Mojo For Chromium Developers1
  8. Qihoo 360 altas 实践
  9. TCP的连接管理
  10. POJ 3863 Business Center