@[江户脱柯北](/space/show?uid=77849) 可能是
by Aleph1022 @ 2018-07-19 19:12:02
你可能需要学学`邻接表`,你这邻接矩阵`MLE`了
by Aleph1022 @ 2018-07-19 19:21:45
@[I_love_him52](/space/show?uid=75840) 谢谢啦,感动中国十大人物啊
by 江户脱柯北 @ 2018-07-19 19:49:49
@[I_love_him52](/space/show?uid=75840) MLE啦?
by 江户脱柯北 @ 2018-07-19 19:50:49
@[I_love_him52](/space/show?uid=75840) 那MLE了几个点呀
by 江户脱柯北 @ 2018-07-19 19:51:10
全部
by Aleph1022 @ 2018-07-19 20:18:16
```cpp
#include <bits/stdc++.h>
#define INF 2147483647
using namespace std;
int a,b,c;
int n,m,s;
int st[10010];
int dis[10010],vis[10010];
struct edge
{
int to,val,next;
} g[500005];
int main()
{
scanf("%d%d%d",&n,&m,&s);
memset(st,-1,sizeof st);
for(int i = 1;i <= m;i++)
{
scanf("%d%d%d",&a,&b,&c);
g[i].to = b;
g[i].next = st[a];
st[a] = i;
g[i].val = c;
}
memset(vis,0,sizeof vis);
for(int i = 1;i <= n;i++)
dis[i] = INF;
dis[s] = 0;
queue<int> q;
q.push(s);
vis[s] = 1;
while(!q.empty())
{
int cur = q.front();
q.pop();
vis[cur] = 0;
for(int i = st[cur];i != -1;i = g[i].next)
{
if(dis[g[i].to] > dis[cur] + g[i].val)
{
dis[g[i].to] = dis[cur] + g[i].val;
if(vis[g[i].to] == 0)
{
q.push(g[i].to);
vis[g[i].to] = 1;
}
}
}
}
for(int i = 1;i <= n;i++)
printf("%d ",dis[i]);
}//邻接表/链式前向星版本
```
by Aleph1022 @ 2018-07-19 20:19:30