Rt 板子会打 但Edge学不明白
自己打了一份不正经的存图方式 样例过了 but 0pts
求大佬指出这种方式的不合理性
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define MAXN 10019
struct l
{
vector<int> bq;//连向的边
vector<int> vq;//边权
} all[MAXN];
struct lx
{
int pos,w;
friend bool operator <(lx x,lx y)
{
return x.w<y.w;
}
} temp;
priority_queue<lx> q;
int dis[MAXN];
bool vi[MAXN];
int n,m,s;
void dij()
{
while(!q.empty())
{
int now=q.top().pos;
q.pop();
if(vi[now]) continue;
vi[now]=true;
for(int i=0;i<all[now].bq.size();i++)
{
dis[all[now].bq[i]]=min(dis[all[now].bq[i]],dis[now]+all[now].vq[i]);
//cout<<"dis["<<all[now].bq[i]<<"]="<<dis[all[now].bq[i]]<<"\n";
temp.pos=all[now].bq[i];
temp.w=all[now].vq[i];
q.push(temp);
}
}
return ;
}
int main()
{
cin>>n>>m>>s;
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
all[u].bq.push_back(v);
all[u].vq.push_back(w);
}
memset(dis,INF,sizeof(dis));
dis[s]=0;
temp.pos=s;
temp.w=0;
q.push(temp);
dij();
for(int i=1;i<=n;i++) cout<<(dis[i]==INF?2147483647:dis[i])<<" ";
return 0;
}