Change of Scenery

Time Limit: 10000ms
Memory Limit: 262144KB

This problem will be judged on CodeForcesGym. Original ID: 100753E
64-bit integer IO format: %I64d      Java class name: (Any)

 
解题:最短路
 #include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int maxn = ;
struct arc{
int to,cost,next;
arc(int x = ,int y = ,int z = -){
to = x;
cost = y;
next = z;
}
}e[];
int head[maxn],cnt[maxn],d[maxn],tot,N,M,K;
void add(int u,int v,int w){
e[tot] = arc(v,w,head[u]);
head[u] = tot++;
}
priority_queue<pii,vector<pii>,greater<pii>>q;
bool done[maxn];
void dijkstra(){
while(!q.empty()) q.pop();
memset(d,0x3f,sizeof d);
memset(cnt,,sizeof cnt);
q.push(pii(d[] = ,cnt[] = ));
while(!q.empty()){
int u = q.top().second;
q.pop();
if(done[u]) continue;
done[u] = true;
for(int i = head[u]; ~i; i = e[i].next){
if(d[e[i].to] > d[u] + e[i].cost){
d[e[i].to] = d[u] + e[i].cost;
cnt[e[i].to] = cnt[u];
q.push(pii(d[e[i].to],e[i].to));
}else if(d[e[i].to] == d[u] + e[i].cost)
cnt[e[i].to]++;
}
}
}
int main(){
int x,u,v,w;
while(~scanf("%d%d%d",&N,&M,&K)){
memset(head,-,sizeof head);
while(K--) scanf("%d",&x);
for(int i = tot = ; i < M; ++i){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
dijkstra();
puts(cnt[N] > ?"yes":"no");
}
return ;
}
/*
3 3 3
1 2 3
1 2 1
2 3 2
1 3 3
4 5 2
1 4
1 2 2
2 4 1
1 3 1
3 4 2
1 4 2
*/

最新文章

  1. Delphi_04_Delphi_Object_Pascal_基本语法_02
  2. connections
  3. 64位系统使用Access 数据库文件的彻底解决方法
  4. imageNamed和imageWithContentsOfFile-无法加载图片的问题
  5. Python profiling
  6. android机型排行榜(201509)
  7. Linux下MySQL使用
  8. linux学习 建立静态库,动态库,写简单的makefile
  9. 纯css兼容个浏览器input[type=&#39;radio&#39;]不能自定义样式
  10. 细说Django的admin
  11. .Net异步关键字async/await的最终理解
  12. zxing开源库的基本使用
  13. android怎么抓取双向认证https的包
  14. [C#]使用Label标签控件模拟窗体标题的移动及窗体颜色不断变换
  15. 用UltraEdit判断打开文件的编码类型 用UltraEdit或notepad记事本查看文件编码格式 用UltraEdit查看当前文件编码
  16. 学习Java的方法
  17. 深入分析JavaWeb Item7 -- HttpServletResponse详解
  18. hdu3951巴什博弈变型
  19. lr中exit(-1)和return 0的区别
  20. MFC/Socket网络编程

热门文章

  1. /bin/bash: jar: command not found(转载)
  2. Django day 37 网站视频的播放,购物车接口,优惠券表分析
  3. 【BZOJ4059】Non-boring sequences(分析时间复杂度)
  4. List 的属性与方法整理
  5. malloc()函数的使用
  6. Android 简单的语音播报
  7. 初始MongoDB------将MongoDB创建为Windows服务
  8. 【sqli-labs】 对于less34 less36的宽字节注入的一点深入
  9. C++为什么抓不到除0错“异常”?
  10. vuex状态管理demo