听取MLE声一片 @ 2020-09-27 21:59:04
Rt，最短路核心思想肯定是熟悉的，蒟蒻想知道如何迅速掌握最短路（以前写的比较少，都是看模板，求教大佬！
顺便求一下用vector建图的SPFA和dij
注：本帖最好不要出现无意义回复
by FutureThx @ 2020-09-27 22:01:05
核心思想都熟悉了，不看模板自己乱打也可以了吧？（另：这个为啥要发灌水）
by 听取MLE声一片 @ 2020-09-27 22:05:47
@Ymw123 乱打打不出来
by 听取MLE声一片 @ 2020-09-27 22:06:08
以后不发灌水了，沉得那么快
by Stay_Hungry @ 2020-09-27 22:07:56
@听取MLE声一片
我提供一种比较舒服的写法：
vector<int> ev[N], ew[N];
void ins(int u, int v, int w) {
ev[u].push_back(v);
ew[u].push_back(w);
}
void solution(int p) {
queue<int> q;
memset(s, 0x3f, sizeof s);
s[p] = 0;
while(!q.empty()) {
int u = q.front(); q.pop();
for(int i = 0; i < ev[u].size(); ++i) {
int v = ev[u][i], w = ew[u][i];
if(s[v] > s[u] + w) {
s[v] = s[u] + w;
q.push(v);
}
}
}
} // SPFA
#define pii pair<int, int>
void solution(int p) {
priority_queue< pii, vector< pii >, greater< pii > > q;
memset(s, 0x3f, sizeof s);
s[p] = 0;
while(!q.empty()) {
int u = q.top().second; q.pop();
for(int i = 0; i < ev[u].size(); ++i) {
int v = ev[u][i], w = ew[u][i];
if(s[v] > s[u] + w) {
s[v] = s[u] + w;
q.push(make_pair(s[v], v));
}
}
}
} // dijby Shiroko @ 2020-09-27 22:08:42
@听取MLE声一片 个人感觉dij和spfa都挺好记的
不过还是上手多打几题才能更好掌握吧
要记就一定要记带优化的 不然以后再想自己在源代码上加优化就晚了（
by SIXIANG32 @ 2020-09-27 22:09:39
@听取MLE声一片 理解原理，多打几遍，就背下来了
by monstersqwq @ 2020-09-27 22:10:36
u1s1这东西我每次打的都不一样，理解了原理就随便写了
by Sktic @ 2020-09-27 22:10:37
先理解原理，然后刷题，尽量不要看模板做，多做就背出来了
by 听取MLE声一片 @ 2020-09-27 22:13:02
谢谢大佬！