题目链接:http://icpc.njust.edu.cn/Problem/Hdu/2066/

SPFA可以高效过,代码如下:

 #include<bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
#define pf printf
#define mem(a,b) memset(a,b,sizeof(a))
#define prime1 1e9+7
#define prime2 1e9+9
#define pi 3.14159265
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define scand(x) scanf("%llf",&x)
#define f(i,a,b) for(int i=a;i<=b;i++)
#define scan(a) scanf("%d",&a)
#define mp(a,b) make_pair((a),(b))
#define P pair<int,int>
#define dbg(args) cout<<#args<<":"<<args<<endl;
#define inf 0x3f3f3f3f
const int maxn=1e4;
int n,m,t,e;
int head[maxn],in[maxn],nxt[maxn],d[maxn],a[maxn],ans,b;
bool vis[maxn];
struct edge{
int v,w;
}p[maxn];
void init()
{
e=;
mem(head,-);
mem(nxt,-);
mem(vis,);
}
void addedge(int u,int v,int w)
{
p[e].v=v;
p[e].w=w;
nxt[e]=head[u];
head[u]=e++;
}
void SPFA(int src)
{
mem(in,);
d[src]=;
queue<int>q;
q.push(src);
in[src]=;
while(!q.empty())
{
int now=q.front();
q.pop();
in[now]=;
for(int i=head[now];~i;i=nxt[i])
{
if(d[p[i].v]>d[now]+p[i].w)
{
d[p[i].v]=d[now]+p[i].w;
if(vis[p[i].v])ans=min(ans,d[p[i].v]);
if(!in[p[i].v])
{
in[p[i].v]=;
q.push(p[i].v);
}
}
}
}
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
std::ios::sync_with_stdio(false);
while(scanf("%d%d%d",&n,&m,&t)!=EOF)
{
init();
ans=inf;
int u,v,w;
f(i,,n)
{
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
f(i,,m)scan(a[i]);
f(i,,t)
{
scan(b);
vis[b]=;
}
f(i,,m)
{
SPFA(a[i]);
}
pf("%d\n",ans);
}
}

最新文章

  1. Java多线程系列--“JUC锁”02之 互斥锁ReentrantLock
  2. [小程序]那些icons
  3. 键盘对应的ASCII码
  4. unity3d的四元数 Quaternion
  5. 谈谈“色彩空间表示方法”——RGB、YUY2、YUYV、YVYU、UYVY、AYUV
  6. YTU 2344: 先序遍历二叉树
  7. js 中 continue 与 break 熟练使用
  8. jquery垂直公告滚动实现代码
  9. 【HDU4391】【块状链表】Paint The Wall
  10. 洛谷-小鱼会有危险吗-BOSS战-入门综合练习2
  11. spring是什么,Spring能帮我们做什么
  12. BZOJ 1004: [HNOI2008]Cards [Polya 生成函数DP]
  13. Typora学习笔记
  14. C# % 和 /
  15. sf2gis@163.com
  16. Qt Dll总结(二)——创建及使用Qt的Dll(转载)
  17. 【BZOJ1055】[HAOI2008]玩具取名(动态规划)
  18. EBS R12 探索之路【EBS 经典SQL分享】
  19. 软件测试(二)PICT的使用 组合测试方法(两两组合测试,可遍历组合测试)
  20. hdoj1232 畅通工程(并查集)

热门文章

  1. Google Play来华 象征意义 跳板而已
  2. 在CodaLab上提交MURA竞赛的结果
  3. POI之下载模板(或各种文件)
  4. 安卓权威编程指南-笔记(第21章 XML drawable)
  5. 【Mood】八上期末考
  6. k8s环境部署本地.net core web项目
  7. 一起了解 .Net Foundation 项目 No.13
  8. 前端每日实战:160# 视频演示如何用纯 CSS 创作一个打开内容弹窗的交互动画
  9. 课题:html5图像羽化(不规则区域羽化,feather,html5羽化)
  10. 前端小微团队的Gitlab实践