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