六百六十六
node为什么要两个变量a
（上课没听
点和距离
距离在边上，总距离在dis里a
idk
好了，说正事，你的代码最新款发一下
@杨浩
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define back_push push_back
#define mian main
using namespace std;
struct e{
int u,v;
};
struct node{
int p,d;
bool operator < (const node & a)const{return a.d>d;}
};
vector<e>mp[500005];
int n,m;
int dis[100005];
bool vis[100005];
void init(){
memset(dis,0x3f,sizeof dis);
cin>>n>>m;
for(int i = 1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
mp[a].back_push({b,c});
}
}
void dijkstra(){
priority_queue<node>q;
dis[1]=0;
q.push((node){1,0});
while(!q.empty()){
node temp = q.top();
q.pop();
int x = temp.p,d = temp.d;
//cout<<x<<" "<<d<<endl;
if(vis[x])continue;
vis[x]=1;
//cout<<mp[1].size();
for(int i = 0;i<mp[x].size();i++){
int tt = mp[x][i].u,ww=mp[x][i].v;
//cout<<"!!!"<<tt<<" "<<ww<<" "<<endl;
if(dis[tt]>dis[x]+ww){
dis[tt]=dis[x]+ww;
if(!vis[tt]){
q.push((node){tt,dis[tt]});
}
}
}
}
}
void write(){
for(int i = 1;i<=n;i++){
if(dis[i] == 0x3f3f3f3f3f3f3f3f){
cout<<"inf ";
}else cout<<dis[i]<<" ";
}
}
void solve(){
init();
dijkstra();
write();
}
signed mian() {
solve();
return 0;
}
没改
我的也炸了
帮我看看
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<bool> vis;
vector<int> dis;
vector<vector<pair<int, int>>> edg;
int main()
{
cin >> n >> m;
priority_queue<pair<int, int>> pq;
edg.resize(n + 1);
dis.resize(n + 1, INT_MAX);
vis.resize(n + 1, 0);
for (int i = 1; i <= m; i++)
{
int u, w, v;
cin >> u >> v >> w;
edg[u].push_back({w, v});
}
dis[1] = 0;
pq.push({0, 1});
while (!pq.empty())
{
auto hd = pq.top();
pq.pop();
if (vis[hd.second])
continue;
vis[hd.second] = 1;
for (auto targ : edg[hd.second])
{
if (dis[hd.second] > dis[targ.second] + targ.first)
{
dis[hd.second] = dis[targ.second] + targ.first;
if (!vis[targ.second])
pq.push({dis[targ.second], targ.second});
}
}
}
for (int i = 1; i <= n; i++)
cout << dis[i] << " ";
return 0;
}
你处理inf了吗
1 个赞
？？？
其他输出就有问题
他开long long了，所以就是0x3f3f3f3f3f3f3f3f
你要不改成SPFA模板吧
SPFA他死了
RE了，喜
虽然这题是dijkstra，但会超时，除非你会dijkstra优化版