ZXmax2005 @ 2024-11-27 22:45:24
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx;
int w[N];
int dist[N];
bool vistied[N];
int n, m;
void add(int a, int b, int c)
{
w[idx] = c;
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({ 0,1 });
while (heap.size())
{
PII k = heap.top();
heap.pop();
int ver = k.second, distance = k.first;
if (vistied[ver]) continue;
vistied[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({ dist[j],j });
}
}
}
for (int i = 1; i <= n; i++)
{
cout << dist[i] << " ";
}
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m;
while (m--)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
dijkstra();
return 0;
}
by szh_AK_all @ 2024-11-27 22:52:51
@ZXmax2005@ZXmax2005
输入的
by ZXmax2005 @ 2024-11-27 23:06:10
@szh_AK_all 是哦,看到数据说明s=1,默认从1开始了,忘记输入s了
by ZXmax2005 @ 2024-11-27 23:08:09
@szh_AK_all添加上s后,10分了,其他全部超时了
by szh_AK_all @ 2024-11-27 23:29:57
@ZXmax2005
把pii换成struct
by ZXmax2005 @ 2024-11-27 23:37:50
@szh_AK_all 改成这样还是超时
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int distance, vertex;
bool operator<(const Node& other) const
{
return distance > other.distance;
}
};
const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx;
int w[N];
int dist[N];
bool visited[N];
int n, m, s;
void add(int a, int b, int c)
{
w[idx] = c;
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[s] = 0;
priority_queue<Node> heap;
heap.push({ 0, s });
while (!heap.empty())
{
Node k = heap.top();
heap.pop();
int ver = k.vertex, distance = k.distance;
if (visited[ver]) continue;
visited[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({ dist[j], j });
}
}
}
for (int i = 1; i <= n; i++)
{
cout << dist[i] << " ";
}
cout << endl;
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m >> s;
while (m--)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
dijkstra();
return 0;
}
by Never_Gone @ 2024-11-29 09:03:54
你的e,ne,w用于存边的话边的范围应该是M=5e5+10
我用你的代码改成
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int distance, vertex;
bool operator<(const Node& other) const
{
return distance > other.distance;
}
};
const int N = 1e5 + 10;
const int M = 5e5 + 10;//这里
int h[N], e[M], ne[M], idx;
int w[M];
int dist[N];
bool visited[N];
int n, m, s;
void add(int a, int b, int c)
{
w[idx] = c;
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[s] = 0;
priority_queue<Node> heap;
heap.push({ 0, s });
while (!heap.empty())
{
Node k = heap.top();
heap.pop();
int ver = k.vertex, distance = k.distance;
if (visited[ver]) continue;
visited[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({ dist[j], j });
}
}
}
for (int i = 1; i <= n; i++)
{
cout << dist[i] << " ";
}
cout << endl;
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m >> s;
while (m--)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
dijkstra();
return 0;
}
就可以过了