coder_want_npy @ 2023-08-16 16:24:38
#include <bits/stdc++.h>
using namespace std;
const int N = 100001;
const int inf = 0x3f3f3f;
struct nod///优先队列存最小距离的点,以知开头,所以记录终点和长度
{
int end;
int length;
};
struct nod1///用vector存零阶矩阵
{
int to;
int len;
};
bool operator<(nod a, nod b)////优先队列小顶堆
{
return a.length < b.length;
}
priority_queue<nod>q;
vector<nod1>dp[N];
long long dis[N];/////dis是记录起点到对应点的最短距离
int vis[N];/////vis记录这个点有没有走过
int n, m, w;//////n是总共几个点,m是几组数据,s点到e的距离为d,w是起点
void dijkstra()
{
memset(dis, inf, sizeof(dis));//////领起点w到每个点的距离为无穷
memset(vis, 0, sizeof(vis));/////每个点都没被遍历过
dis[w] = 0;/////起点到起点的距离为0
nod y;
y.end = w;
y.length = 0;
q.push(y);
while (!q.empty())
{
int top = q.top().end;
q.pop();
if(vis[top])
{
continue;
}
for(int i=0;i<dp[top].size();i++)
{
int end_ = dp[top][i].to;
int length_ = dp[top][i].len;
dis[end_] = min(dis[end_], dis[top] + length_);
nod temp;
temp.end = end_;
temp.length = length_;
q.push(temp);
}
vis[top] = 1;
}
}
int main()
{
cin >> n >> m >> w;
for (int i = 1; i <= m; i++)
{
int s, e, d;
cin >> s >> e >> d;
nod1 t;
t.to = e;
t.len = d;
dp[s].push_back(t);///s点到e点的距离为d
}
dijkstra();
for (int i = 1; i <= n; i++)
{
cout << dis[i] << " ";
}
}
by coder_want_npy @ 2023-08-16 16:26:32
说错了,用的是邻接表vector
by zhaoyp @ 2023-08-16 16:29:03
你的 q.push 这一块写的是什么玩意儿啊