Luckies @ 2022-12-31 10:37:59
有没有用vector存图的啊，蒟蒻不会链式前向星
by Cerisier @ 2022-12-31 10:40:52
#include <cstring>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
using namespace std;
const int maxn = 1e5 + 10;
int inf;
struct node {
int v, w;
node(int vv, int ww) { v = vv, w = ww; }
};
vector<node> g[maxn];
int d[maxn];
int n, m, s;
queue<int> q;
bool in_queue[maxn];
void spfa(int s) {
memset(d, 0x3f, sizeof(d));
inf = d[1];
d[s] = 0;
in_queue[s] = true;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
in_queue[u] = false;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i].v;
if (d[v] > d[u] + g[u][i].w) {
d[v] = d[u] + g[u][i].w;
if (!in_queue[v]) {
q.push(v);
}
}
}
}
}
set<pair<int, int> > min_heap;
void dij(int s) {
memset(d, 0x3f, sizeof(d));
inf = d[1];
d[s] = 0;
min_heap.insert(make_pair(d[s], s));
while (!min_heap.empty()) {
int mind = min_heap.begin()->first;
int u = min_heap.begin()->second;
min_heap.erase(min_heap.begin());
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i].v;
if (d[v] > d[u] + g[u][i].w) {
min_heap.erase(make_pair(d[v], v));
d[v] = d[u] + g[u][i].w;
min_heap.insert(make_pair(d[v], v));
}
}
}
}
int main() {
cin >> n >> m >> s;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back(node(v, w));
}
dij(s);
for (int i = 1; i <= n; i++) {
if (d[i] == inf) {
cout << 2147483647 << ' ';
} else {
cout << d[i] << ' ';
}
}
return 0;
}by Cerisier @ 2022-12-31 10:40:59
@Stephen__Curry
by joyslog @ 2022-12-31 10:41:54
完全可以用 std::vector。
建边：
struct Edge {int u, v, w;};
vector<Edge> edges;
vector<int> G[MAX_N];
inline void AddEdge(int u, int v, int w) {
edges.push_back({u, v, w});
G[u].push_back(edges.size() - 1);
}遍历：
for(int i = 0; i < G[u].size(); i++) {
int v = edges[G[u][i]].v, w = edges[G[u][i]].w;虽然常数确实略大，但是没被卡过。
by scp020 @ 2022-12-31 10:49:32
dijkstra+堆优化，vector存图。
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
struct edge{int to,cost;};
vector<edge> g[200010];
int f[200010],v[200010],pos,n,m,s;
priority_queue< pair<int,int> > q;
void dijkstra(int s)
{
for(int i=1;i<=n;i++) f[i]=inf;
f[s]=0;
q.push(make_pair(0,s));
while(!q.empty())
{
pos=q.top().second,q.pop();
if(v[pos]) continue;
v[pos]=1;
for(int i=0,x,y;i<g[pos].size();i++)
{
x=g[pos][i].to,y=g[pos][i].cost;
if(f[x]>f[pos]+y) f[x]=f[pos]+y,q.push(make_pair(-f[x],x));
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
for(int i=1,x,y,z;i<=m;i++) scanf("%d%d%d",&x,&y,&z),g[x].push_back((edge){y,z});
dijkstra(s);
for(int i=1;i<=n;i++) printf("%d ",f[i]);
return 0;
}by ssilrrr @ 2022-12-31 11:25:30
一直用vector存图。
还有遍历的时候更方便的办法：直接存pair。
for(auto [v,w]:v[u])by Luckies @ 2022-12-31 11:32:03
蟹蟹大家，我用vector存图一直过不了样例
by Luckies @ 2022-12-31 11:32:23
刚刚才过的
by Ruiqun2009 @ 2023-01-07 23:07:53
其实我写也是用结构化绑定+vector 存图+手写堆。
#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
#include <utility>
#include <stdexcept>
#include <queue>
constexpr int MAXN = 100005;
template <size_t __length>
class my_bitset32 {
unsigned _M_arr[(__length + 31) >> 5] = {0};
static_assert(__length >= 1, "");
public:
inline _GLIBCXX14_CONSTEXPR my_bitset32(unsigned long long val = 0) noexcept {
if _GLIBCXX17_CONSTEXPR (__length >= 2) {
_M_arr[1] = val & ((1ull << 32ull) - 1ull);
_M_arr[0] = val >> 32ull;
}
else _M_arr[0] = val & ((1ull << 32ull) - 1ull);
}
class reference {
size_t _M_pos;
friend class my_bitset32<__length>;
unsigned* ptr;
inline _GLIBCXX_CONSTEXPR reference() {}
public:
reference(my_bitset32<__length>& b, size_t pos) noexcept {
_M_pos = pos & 31;
ptr = b._M_arr + (pos >> 5);
}
inline _GLIBCXX_CONSTEXPR operator bool() const noexcept { return (*(ptr) & (1 << _M_pos)) != 0; }
inline _GLIBCXX_CONSTEXPR bool operator~() const noexcept { return (*(ptr) & (1 << _M_pos)) == 0; }
inline _GLIBCXX14_CONSTEXPR reference& flip() noexcept {
*ptr ^= (1 << _M_pos);
return *this;
}
inline _GLIBCXX14_CONSTEXPR reference& operator=(bool v) noexcept {
if (v) *ptr |= (1 << _M_pos);
else *ptr &= ~(1 << _M_pos);
return *this;
}
~reference() {}
inline _GLIBCXX14_CONSTEXPR reference(const reference&) = default;
};
friend class reference;
public:
#if __cplusplus > 202002L
constexpr
#endif
inline reference operator[](size_t index) { return reference(*this, index); }
inline _GLIBCXX_CONSTEXPR bool operator[](size_t index) const { return (bool)reference(*this, index); }
inline _GLIBCXX_CONSTEXPR size_t size() const noexcept { return __length; }
inline size_t count() const noexcept {
size_t ans = 0;
for (size_t i = 0; i < ((__length + 31) >> 5); i++) ans += __builtin_popcount(_M_arr[i]);
return ans;
}
inline bool test(size_t pos) const {
if (pos >= size()) throw std::out_of_range("my_bitset32::test");
return this->operator[](pos);
}
inline bool all() const noexcept {
for (size_t i = 0; i < ((__length + 31) >> 5); i++) if (__builtin_popcount(_M_arr[i]) != 32) return false;
return true;
}
inline bool none() const noexcept {
for (size_t i = 0; i < ((__length + 31) >> 5); i++) if (__builtin_popcount(_M_arr[i]) != 0) return false;
return true;
}
inline bool any() const noexcept {
for (size_t i = 0; i < ((__length + 31) >> 5); i++) if (__builtin_popcount(_M_arr[i]) != 0) return true;
return false;
}
inline _GLIBCXX14_CONSTEXPR my_bitset32<__length>& operator&=(const my_bitset32<__length>& other) noexcept {
for (size_t i = 0; i < ((__length + 31) >> 5); i++) _M_arr[i] &= other._M_arr[i];
return *this;
}
inline _GLIBCXX14_CONSTEXPR my_bitset32<__length>& operator|=(const my_bitset32<__length>& other) noexcept {
for (size_t i = 0; i < ((__length + 31) >> 5); i++) _M_arr[i] |= other._M_arr[i];
return *this;
}
inline _GLIBCXX14_CONSTEXPR my_bitset32<__length>& operator^=(const my_bitset32<__length>& other) noexcept {
for (size_t i = 0; i < ((__length + 31) >> 5); i++) _M_arr[i] ^= other._M_arr[i];
return *this;
}
inline _GLIBCXX14_CONSTEXPR my_bitset32<__length> operator~() const noexcept {
my_bitset32<__length> res;
for (size_t i = 0; i < ((__length + 31) >> 5); i++) res._M_arr[i] = ~_M_arr[i];
for (size_t i = (__length & 31); i < 32; i++) res._M_arr[__length >> 5] &= ~(1 << i);
return res;
}
inline void reset() { memset(_M_arr, 0, ((__length + 31) >> 5) * sizeof(unsigned)); }
};
std::vector<std::pair<int, int> > e[MAXN];
int d[MAXN];
my_bitset32<MAXN> vis;
char c;
constexpr size_t READ_MAXN = 1 << 16;
constexpr size_t READ_ARR_SIZE = READ_MAXN | 5;
char inbuf[READ_ARR_SIZE], outbuf[READ_ARR_SIZE];
char *curinpos = inbuf + READ_MAXN, *curoutpos = outbuf;
char *end_inbuf = inbuf + READ_MAXN, *end_outbuf = outbuf + READ_MAXN;
inline char gc() {
if (curinpos == end_inbuf) {
end_inbuf = inbuf + fread(inbuf, 1, READ_MAXN, stdin);
curinpos = inbuf;
}
return *curinpos++;
}
inline void pc(char x) {
if (curoutpos == end_outbuf) {
fwrite(outbuf, 1, READ_MAXN, stdout);
curoutpos = outbuf;
end_outbuf = outbuf + READ_MAXN;
}
*curoutpos++ = x;
}
inline unsigned readuint() {
unsigned eax(0);
c = gc();
while (!isdigit(c)) c = gc();
while (isdigit(c)) eax = (eax << 3) + (eax << 1) + (c & 15), c = gc();
return eax;
}
inline void putuint(unsigned x) {
static char buf[15];
static unsigned curpos;
curpos = 0;
do {
buf[curpos++] = (x % 10) | 48;
x /= 10;
} while (x);
while (curpos--) pc(buf[curpos]);
}
std::pair<unsigned, unsigned> heap[MAXN];
unsigned tot = 0;
inline void my_swap(unsigned& a, unsigned& b) { a ^= b ^= a ^= b; }
inline void my_swap(std::pair<unsigned, unsigned>& a, std::pair<unsigned, unsigned>& b) {
my_swap(a.first, b.first);
my_swap(a.second, b.second);
}
inline void __push(unsigned pos = tot) {
while (pos > 1 && heap[pos] < heap[pos >> 1]) {
my_swap(heap[pos], heap[pos >> 1]);
pos >>= 1;
}
}
inline void __adjust(unsigned pos = 1) {
unsigned tar = pos << 1;
while (tar <= tot) {
if (tar < tot) tar = heap[tar] < heap[tar | 1] ? tar : (tar | 1);
if (heap[pos] > heap[tar]) my_swap(heap[pos], heap[tar]);
else break;
pos = tar;
tar = pos << 1;
}
}
inline void push(const std::pair<unsigned, unsigned>& x) {
heap[++tot] = x;
__push();
}
inline void pop() {
my_swap(heap[1], heap[tot--]);
__adjust();
}
inline void add(int u, int v, int w) { e[u].emplace_back(v, w); }
inline void dij(unsigned s) {
push(std::make_pair(0, s));
memset(d, 0x3f, MAXN * sizeof(unsigned));
vis.reset();
d[s] = 0;
while (tot) {
int u = heap[1].second;
pop();
if (vis[u]) continue;
vis[u] = true;
for (auto [v, w] : e[u]) if (d[v] > d[u] + w) {
d[v] = d[u] + w;
push(std::make_pair(d[v], v));
}
}
}
unsigned n, m, S;
void Read() {
n = readuint(), m = readuint(), S = readuint();
unsigned u, v, z;
for (unsigned i = 1; i <= m; i++) {
u = readuint(), v = readuint(), z = readuint();
add(u, v, z);
}
}
void Solve() {
dij(S);
for (unsigned i = 1; i <= n; i++) putuint(d[i] == 0x3f3f3f3f ? 2147483647 : d[i]), pc(' ');
}
int main() {
Read();
Solve();
fwrite(outbuf, 1, curoutpos - outbuf, stdout);
return 0;
}