记录编号	516522	评测结果	AAAAAAAAAAA
题目名称	[福州培训2010] 最短路	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	0.055 s
提交时间	2018-10-25 13:09:04	内存使用	0.32 MiB

#include<bits/stdc++.h>
using namespace std;
const int INF=1000000;
int m,n,k;
bool inque[101];
queue<int> que;
struct node
{ int t,dist;
};
vector<node> g[101];
int d[101];
void spfa(int s)
{ memset(inque,0,sizeof(inque));
  memset(d,INF,sizeof(d));
  d[s]=0;
  inque[s]=true;
  que.push(s);
  while (!que.empty())
  { int u=que.front();
    que.pop();
    inque[u]=false;
    for (int i=0;i<g[u].size();i++)
    { int v=g[u][i].t;
      int w=g[u][i].dist;
      if (d[u]+w<d[v]) { d[v]=d[u]+w;
                         if (!inque[v])
                         { que.push(v);
                           inque[v]=true;
						 }
	  }
	}
  }
}
int main()
{ freopen("shorta.in","r",stdin);
  freopen("shorta.out","w",stdout);
  scanf("%d%d",&n,&m);
  for (int i=1;i<=m;i++)
  { int x,y,z;
    scanf("%d%d%d",&x,&y,&z);
    g[x].push_back((node){y,z});
    g[y].push_back((node){x,z});
  }
  for (int i=1;i<=n;i++)
  { spfa(i);
    for (int j=1;j<=n;j++)
    printf("%d ",d[j]);
    cout<<endl;
  }
  return 0;
}