此题中起点有1000个,边有20000条。用链式前向星建图,再枚举起点用SPFA的话,超时了。(按理说,两千万的复杂度应该没超吧。不过一般说计算机计算速度 1~10 千万次/秒。也许拿最烂的计算机来卡时间)

  有一个技巧,加一个超级源点。也就是加一个点,使得该点连通所有的起点,并且边的权值为0。这个技巧应用蛮多的。网络流、最小树形图都有题目这样做。

 

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N = , M=;
const int INF = 0x3f3f3f3f;
struct node
{
int to, w, next;
};
node edge[M];
int head[N], dist[N], outq[N];
bool vis[N];
int tot;
bool SPFA(int s, int n )
{
int i,k;
for(i=;i<=n;i++) dist[i]=INF;
memset(vis,,sizeof(vis));
memset(outq,,sizeof(outq));
queue<int > q;
while(!q.empty()) q.pop();
vis[s]=;
dist[s]=;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=;
outq[u]++;
if(outq[u]>n) return ;
k=head[u];
while(k>=)
{
if(dist[edge[k].to]-edge[k].w>dist[u])
{
dist[edge[k].to]=dist[u]+edge[k].w;
if(!vis[edge[k].to])
{
vis[edge[k].to]=;
q.push(edge[k].to);
}
}
k=edge[k].next;
}
}
return ;
}
void addedge(int i,int j,int w)
{
edge[tot].to=j;
edge[tot].w=w;
edge[tot].next=head[i];
head[i]=tot++;
}
void init()
{
tot=;
memset(head,-,sizeof(head));
}
int main()
{
//freopen("test.txt","r",stdin);
int i,j,k,n,m,t,s;
while(scanf("%d%d%d",&n,&m,&t)!=EOF)
{
init();
while(m--)
{
scanf("%d%d%d",&i,&j,&k);
addedge(i,j,k);
}
scanf("%d",&k);
for(i=;i<k;i++)
{
scanf("%d",&s);
addedge(n+,s,);
}
SPFA(n+,n+);
if(dist[t]==INF) printf("-1\n");
else printf("%d\n",dist[t]);
}
return ;
}

最新文章

  1. Xamarin体验:使用C#开发iOS/Android应用
  2. Oil Deposits
  3. thinking in object pool
  4. RPI学习--环境搭建_串口连接
  5. python版恶俗古风自动生成器.py
  6. Workflow_如何处理标准异常和自定义异常(案例)
  7. hdu 5569 matrix(简单dp)
  8. 在Myeclipse中用Java语言操作mysql数据库
  9. ProgressDialog替代
  10. Spring webflux
  11. 简单快速的Android打渠道包的方法
  12. html 获取数据并发送给后端方式
  13. asp.net 访问页面访问统计实现
  14. 开发框架DevExtreme全新发布v18.2.6|附下载
  15. JSON数据的处理中的特殊字符
  16. mybatis入门--mapper代理方式开发
  17. [udemy]WebDevelopment_How the Internet Works
  18. centos7 rabbitmq安装以及应用
  19. Unity发布Windows程序遇到的问题
  20. 阿里云短信接口python版本

热门文章

  1. Scala语言学习笔记——方法、函数及异常
  2. day009 文件操作
  3. transparent
  4. pytorch实战(7)-----卷积神经网络
  5. C# 通过反射为一个对象赋值
  6. 关于autoupgader的狗屎问题
  7. 【ACM】NYOJ_506_洗澡_20130725
  8. redis-快照
  9. nodejs-n-nvm版本管理工具
  10. cogs 9. 中心台站建设。。。