这题我必须要发个题解。
因为
我爆int了
这么个破数怎么会爆int呢
因为我把最大值设成了2147483647
出来了负数,然而我还不明白调了半个小时
所以吸取经验教训,在一个不可能出现负数的程序里如果出现负数就很有可能是爆int了鸭
#include<bits/stdc++.h>
#define read(x) scanf("%d",&x)
using namespace std;
const int M = 1e5+5;
const int N = 1e5+5;
const int INF = 1e9;//比较保险
int n,m,cnt,first[M],dist[N];
bool r[N];
struct edge {
int end,nxt,len;
}bian[M];
void addedge(int s,int e,int w) {
cnt++;
bian[cnt].end = e;
bian[cnt].len = w;
bian[cnt].nxt = first[s];
first[s] = cnt;
}
priority_queue<pair<int,int> > h;
void dijkstra(int s) {
dist[s] = 0;
for(register int i=1; i<=n; i++) h.push(make_pair(-dist[i],i));
for(register int i=1; i<=n; i++) {
while(r[h.top().second]) h.pop();
int s = h.top().second;
r[s] = 1;
h.pop();
for(register int x=first[s]; x!=0; x=bian[x].nxt) {
int e = bian[x].end;
int l = bian[x].len;
int newl = dist[s]+l;
if(newl<dist[e]) {
dist[e] = newl;
h.push(make_pair(-dist[e],e));
}
}
}
}
int main() {
read(n),read(m);
for(register int i=1; i<=m; i++) {
int s,e,l;
read(s),read(e),read(l);
addedge(s,e,l);
}
for(register int i=1; i<=n; i++) dist[i] = INF;
dijkstra(1);
if(dist[n]==INF || dist[n]<0) printf("-1\n");
//这里判个负数丷,double保险
else printf("%d\n",dist[n]);
return 0;
}
完结吐槽
为什么我dijkstra I过了II不过
建议加强I的数据叭
一般初始化都是memset(dist, 0x3f, sizeof dist);
memset很慢的,在数据范围较大的时候会TLE(血的教训)
不都O(n)吗
我不太记时间复杂度诶(大雾)反正有一次我memsetTLE了,赛后改成for就AC了
可能是 CF 的 sum (n) = 1e5之类的,所以会TLE。一般来说 memset不应该稍微比 O(N) 快点吗
那次比赛220->170之后我就再也没用过memset(%%%墨染空大佬)
所以保险点循环赋值吗,csp会卡这些吗?
我和我的队友们遇到好多memset导致的TLE,还是for一边保险吧(CSP刚出现谁知道它卡不卡呢,一般不会故意卡吧我觉得,但是要是你算法写的比较烂这个可以稍微优化一点八)
woc我在网上搜了下,都说memset效率比for一遍高多了。。。
行吧。。我在回复你之前也搜了一下好多人说for比较保险。。我觉得用多少初始化多少的话还是for快,这算个人习惯吧。。
应该不会吧,毕竟csp没有出过 sum(n) = 1e5 之类的。所以基本上每次memset是与你的时间复杂度同阶的
sum(n) = 1e5是什么意思?
同问
就是说给给多组数据(<=100000),比如每组数据有可能读100000个数。
很明显极限数据肯定超时。所以他还会规定 读入的数据量总和不超过 100000
这是时候如果memset 复杂度就是T*数组大小了,所以会爆
哦哦,我之前遇到的就是多组数据然后询问次数很多