talks are cheep,show I the codes
by fjy666 @ 2021-07-01 16:25:47
@[fjy666](/user/366338) `show me the codes`
by _l_l_l_l_l_ @ 2021-07-01 17:06:16
@[miserExist](/user/49677) 试试用$queue$(听说$queue$快一点)
实在不行开$O2$
by _l_l_l_l_l_ @ 2021-07-01 17:07:19
用$scanf$输入
by _l_l_l_l_l_ @ 2021-07-01 17:13:49
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 * 3 + 109;
int n,ml,md;
int h[N], e[N], ne[N], w[N], idx = 1;
int d[N], cnt[N];
int in_queue[N];
void add(int a,int b,int c)
{
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++;
}
void spfa(int s)
{
//queue<int> q;
deque<int> q;
memset(in_queue, 0, sizeof in_queue);
memset(cnt, 0, sizeof cnt);
d[s] = 0;
q.push_back(s);
in_queue[s] = 1;
while(!q.empty())
{
int x = q.back();
q.pop_back();
in_queue[x] = 0;
for(int i = h[x]; ~i; i = ne[i])
{
int y = e[i];
if(d[y] > d[x] + w[i])
{
d[y] = d[x] + w[i];
cnt[y] = cnt[x] + 1;
if(cnt[y] >= n + 1)
{
puts("-1");
exit(0);
}
if(!in_queue[y])
{
in_queue[y] = 1;
q.push_back(y);
}
}
}
}
}
int main()
{
memset(d, 0x3f, sizeof d);
int INF = d[0];
memset(h, -1, sizeof h);
cin >> n >> ml >> md;
for(int i = 1; i <= ml; i ++)
{
//b - a <= d
//(a,b,d);
int a,b,c;
scanf("%d%d%d", &a, &b, &c);
add(a,b,c);
}
for(int i = 1; i <= md; i ++)
{
//b - a >= d
// a <= b - d
//(b,a,-d);
int a,b,c;
scanf("%d%d%d", &a, &b, &c);
add(b,a,-c);
}
for(int i = 1; i <= n; i ++)
{
add(0,i,0);
}
for(int i = 1; i <= n; i ++)
{
add(i + 1, i, 0);
}
spfa(0);
memset(d, 0x3f, sizeof d);
spfa(1);
if(d[n] == INF)
{
puts("-2");
return 0;
}
//cout << 0x3f << endl;
cout << d[n] << endl;
return 0;
}
```
by miserExist @ 2021-07-01 17:22:15
可能deque查负环快一点
这道题点数偏多?
by miserExist @ 2021-07-01 17:23:18
@[WenZKbb](/user/522828)
@[fjy666](/user/366338)
by miserExist @ 2021-07-01 17:25:37
调好了，问题如下：
```
cnt[y] = cnt[x] + 1;
```
是错误的， 应改为：
```
cnt[y]++;
```
并将$cnt[s]$的处置设为1。
2. 每一步取前面的点，而不是后面的点。
by Nuclear_Pasta @ 2022-09-20 21:03:25
[改后代码。](https://www.luogu.com.cn/paste/7hxicpyu)
by Nuclear_Pasta @ 2022-09-20 21:04:33
@[miserExist](/user/49677) 问题如上，不用换成queue,deque反而会快些。
by Nuclear_Pasta @ 2022-09-24 17:08:42