不退 (UID: 125397)
注册于 7 年前, 最后登录于 6 年前, 目前离线.
解决了 2 道题目，RP: 196.17 (No. 6)
- 讨论 (0)
- 贡献 (0)
- 递交 (2)
最近递交
| 状态 | 题目 | 递交者 | 时间 | 内存 | 语言 | 递交时间 |
|---|
| P2029 时间复杂度 | 不退 | 18ms | 320.0 KiB | C++ | 6 年前 | |
| 抓住那头牛 | 不退 | 23ms | 2.367 MiB | C++ | 6 年前 | |
| 抓住那头牛 | 不退 | 21ms | 384.0 KiB | C++ | 6 年前 | |
| P1179 邮票面值设计 | 不退 | 122ms | 384.0 KiB | C++ | 6 年前 | |
| P1179 邮票面值设计 | 不退 | 149ms | 384.0 KiB | C++ | 6 年前 | |
| lxy 搭积木 | 不退 | 46ms | 384.0 KiB | C++ | 6 年前 | |
| 4399小游戏之 十字架 | 不退 | 48ms | 384.0 KiB | C++ | 6 年前 | |
| P1926 紫色的手链 | 不退 | 301ms | 484.0 KiB | C++ | 6 年前 | |
| P1926 紫色的手链 | 不退 | 228ms | 472.0 KiB | C++ | 6 年前 | |
| P1926 紫色的手链 | 不退 | 355ms | 512.0 KiB | C++ | 6 年前 |
个人简介
#include<iostream>
using namespace std;
const int INF=0x3f3f3f3f;
int n,m,s,u,v,w,cnt;
int queue[100005],head[10005],dis[10005];
bool vis[10005];
struct edge{
int to;
int next;
int val;
}a[500005];
void add(int u,int v,int w)
{
a[++cnt].to=v;
a[cnt].val=w;
a[cnt].next=head[u];
head[u]=cnt;
}
void spfa()
{
int u,l=0,r=1;
queue[1]=s;
vis[s]=1;
dis[s]=0;
while(l<r)
{
u=queue[++l];
vis[u]=0;
for(int i=head[u];i;i=a[i].next)
{
if(dis[u]+a[i].val<dis[a[i].to])
{
dis[a[i].to]=dis[u]+a[i].val;
if(vis[a[i].to]==0)
{
vis[a[i].to]=1;
queue[++r]=a[i].to;
}
}
}
}
}
int main()
{
cin>>n>>m>>s;
for(int i=1;i<=n;++i)
dis[i]=INF;
dis[s]=0;
for(int i=1;i<=m;++i)
{
cin>>u>>v>>w;
add(u,v,w);
}
spfa();
for(int i=1;i<=n;++i)
{
if(dis[i]==INF)
cout<<2147483647<<" ";
else
cout<<dis[i]<<" ";
}
return 0;
}