为什么排版变成了这样?
by 天下第一！ @ 2019-03-18 20:31:21
希望更丰富的展现？使用Markdown
by Kan_kiz @ 2019-03-18 20:32:36
```cpp
#include<bits/stdc++.h>
using namespace std;
int maxx=2147483647;
int n,i,j,minl,k,m,s,x,y,z;
int c[10001],f[10001][10001];
bool b[10001];
int main(){
cin>>n>>m>>s;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
f[i][j]=maxx;
for(i=1;i<=m;i++){
cin>>x>>y>>z;
f[x][y]=z;
f[y][x]=z;
}
for(i=1;i<=n;i++) c[i]=f[s][i];
memset(b,false,sizeof(b));
b[s]=true;
c[s]=0;
for(i=1;i<n;i++){
minl=maxx;
k=0;
for(j=1;j<=n;j++)
if((!b[j])&&(c[j]<minl)){
minl=c[j];
k=j;
}
if(k==0) break;
b[k]=true;
for(j=1;j<=n;j++)
if(c[k]+f[k][j]<c[j])
c[j]=c[k]+f[k][j];
}
for(i=1;i<=n;i++)
cout<<c[i]<<" ";
cout<<endl;
return 0;
}
```
by Sai0511 @ 2019-03-18 20:32:41
@[Sai_0511](/space/show?uid=114320) 太棒了，谢谢大佬
by 天下第一！ @ 2019-03-18 20:33:47
我是用手机发的
by 天下第一！ @ 2019-03-18 20:34:13
@[天下第一！](/space/show?uid=54101) 二维数组建议最大开5000*5000，你的f数组越界了
by Timing @ 2019-03-18 20:42:11
@[天下第一！](/space/show?uid=54101) 如果没有其他问题，建议学习一下用小根堆实现dijkstra
by Timing @ 2019-03-18 20:43:05
@[Timing](/space/show?uid=130161) 建议用邻接表存图（一般情况下会好很多）
by Timing @ 2019-03-18 20:44:58
@[天下第一！](/space/show?uid=54101)
- 我打的（邻接表存图+优先队列）
```cpp
#include<bits/stdc++.h>
using namespace std;
const int M=500005;
int s;
typedef pair<int,int> P;//二元组
int head[M],cnt,nxt[M],to[M],w[M],vis[M],dis[M];
void add(int u,int v,int val){
nxt[++cnt]=head[u];
to[cnt]=v;
w[cnt]=val;
head[u]=cnt;
}
priority_queue<P,vector<P>,greater<P> > Q;
//优先队列是大根堆，用greater改为小根堆
void dij(){
dis[s]=0;
Q.push(P(0,s));
while(!Q.empty()){
int u=Q.top().second;
Q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(vis[v]) continue;
if(dis[v]>dis[u]+w[i]){
dis[v]=dis[u]+w[i];
if(!vis[v])
Q.push(P(dis[v],v));
}
}
}
}
int n,m;
int main(){
ios::sync_with_stdio(false);
cin>>n>>m>>s;
int u,v,val;
for(int i=1;i<=m;i++){
cin>>u>>v>>val;
add(u,v,val);
}
memset(dis,0x7f,sizeof(dis));
dij();
for(int i=1;i<=n;i++){
if(dis[i]>99999999)cout<<2147483647<<' ';
else cout<<dis[i]<<' ';
}
cout<<endl;
return 0;
}
```
by Timing @ 2019-03-18 20:48:09
谢谢大佬，我学习一下！
by 天下第一！ @ 2019-03-18 21:43:17