考试的T3,拿暴力+剪枝卡过去了.

没想到 CF 上也能过 ~

code:

#include <bits/stdc++.h>
#define N 100004
#define LL long long
#define inf 1000000000000000
using namespace std;
int go[N];
namespace IO
{
char *p1, *p2, buf[100000];
#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )
inline int rd() {
int x = 0;
char c = nc();
while (c < 48) {
c = nc();
}
while (c > 47) {
x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();
}
return x;
}
inline void setIO(string s)
{
string in=s+".in";
string out=s+".out";
freopen(in.c_str(),"r",stdin);
freopen(out.c_str(),"w",stdout);
}
};
LL d[N];
vector<int>G[N];
int n,m,Q,done[N],inq[N];
struct edge
{
LL val;
int u,v;
}ee[N];
deque<int>q;
void dijkstra()
{
for(int i=1;i<=n;++i) d[i]=inf,inq[i]=0;
d[1]=0, inq[1]=1;
q.push_back(1);
while(!q.empty())
{
int u=q.front(); q.pop_front();
for(int i=G[u].size()-1;i>=0;--i)
{
edge e=ee[G[u][i]];
inq[e.u]=0;
if(d[e.v]>d[u]+e.val)
{
d[e.v]=d[u]+e.val;
if(!inq[e.v])
{
if(q.empty()||d[e.v]<d[q.front()]) q.push_front(e.v);
else q.push_back(e.v);
inq[e.v]=1;
}
}
}
}
}
int main()
{
// int t=clock();
// IO::setIO("input");
int i,j,flag=1;
n=IO::rd();
m=IO::rd();
Q=IO::rd();
// scanf("%d%d%d",&n,&m,&Q);
for(i=1;i<=m;++i)
{
ee[i].u=IO::rd();
ee[i].v=IO::rd();
ee[i].val=IO::rd();
G[ee[i].u].push_back(i);
}
dijkstra();
for(i=1;i<=n;++i) if(d[i]==inf) go[i]=0; else go[i]=1;
for(i=1;i<=Q;++i)
{
int opt,pp;
opt=IO::rd();
pp=IO::rd();
// scanf("%d%d",&opt,&pp);
if(opt==2)
{
for(j=1;j<=pp;++j)
{
int x=IO::rd();
++ee[x].val;
}
flag=0;
}
else
{
if(!go[pp])
{
printf("-1\n");
}
else
{
if(!flag)
{
flag=1;
dijkstra();
}
printf("%lld\n",d[pp]);
}
}
}
// printf("%d\n",clock()-t);
return 0;
}

  

最新文章

  1. 更新/替换系统 hosts,轻松访问国外站点
  2. redis安装
  3. C# Graphics类详解
  4. ORM系列之一:Dos.ORM
  5. android设备休眠机制
  6. Hibernate-细细道来-01
  7. Codechef2015 May - Chef and Strings (后缀自动机)
  8. OpenCV2马拉松第14圈——边缘检測(Sobel,prewitt,roberts)
  9. mysql学习(五)-字段属性
  10. android双击返回键退出程序
  11. 基于科大讯飞语音云windows平台开发
  12. 读书笔记 effective C++ Item 40 明智而谨慎的使用多继承
  13. [Swift]LeetCode292. Nim游戏 | Nim Game
  14. OrCAD Capture CIS 16.6 在原理图页面内放置图片
  15. Office_PPT_让你一分钟完成上百张图片的快速保存
  16. 比较perl+python
  17. SpringMvc中controller之间的方法调用
  18. 转:iBatis简单入门教程
  19. Axure 8.0.0.3312下载地址以及注册码
  20. 20155229实验二 《Java面向对象程序设计》实验报告

热门文章

  1. littleFS在RT1052移植笔记
  2. go 实现简单的http web服务
  3. Python开发【第二章】:模块和运算符
  4. 米联客 osrc_virtual_machine_sdx2017_4 虚拟机的使用
  5. Student&#39;s Camp CodeForces - 708E (dp,前缀和优化)
  6. 手把手教小白安装Erlang
  7. C#汉字转换成全拼的拼音
  8. springboot_2
  9. 利用python爬取王者荣耀英雄皮肤图片
  10. Vue父组件向子组件传递方法(自定义方法)并且子组件向父组件传递数据