0
中级光能
//90分错误代码
#include<bits/stdc++.h>
#define MAXN 105
#define INF 2000000000000
using namespace std;
struct edge{
long long adj,w;
};
queue<long long> q;
vector<edge> g[MAXN];
long long n,dis[MAXN];
bool exist[MAXN];
void SPFA(long long s){
for(int i=1;i<=n;i++)
dis[i]=INF;
dis[s]=0;
q.push(s);
exist[s]=true;
while(!q.empty()){
int idx=q.front();
q.pop();
exist[idx]=false;
for(int i=0;i<g[idx].size();i++){
edge e=g[idx][i];
if(dis[e.adj]>dis[idx]+e.w){
dis[e.adj]=dis[idx]+e.w;
if(!exist[e.adj]){
exist[e.adj]=true;
q.push(e.adj);
}
}
}
}
}
int main(){
cin>>n;
int st;
cin>>st;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
string s;
stringstream ss;
cin>>s;
ss<<s;
int x;
if(ss>>x){
g[i].push_back((edge){j,x});
}
}
}
SPFA(st);
for(int i=1;i<=n;i++){
if(st!=i){
printf("(%.d -> %.d) = %.d\n",st,i,dis[i]);
}
}
return 0;
}
刚学图论的小蒟蒻，恳请各位大佬能指点出我哪里错了，谢谢
陶旭杰在2020-07-26 12:16:54追加了内容
@酷町喵~o( =∩ω∩= )o~ @张睿杰 @葛新 求解丫！
1
初级守护
第二行改成:
#define INF 2000000000000LL
0
高级守护
同学，图论第一保命要素，long long啊，兄弟
0
中级天翼
long long!!!
0
资深光能
迪杰斯特拉算法
0
中级天翼
what!!!???宏定义？（我还没学）
0
中级启示者
最短路径算法（floyed）
0
新手光能
我不会呀
0
初级天翼
1
0
初级光能
long long
0
中级光能
long long
0
初级守护
long long!!!!!
int 不够！！！! !
结果保证在64位二进制整型范围内。
0
资深光能
动态规划
实在不会来个DFS
0
高级光能
用long long，初值赋大一点。
0
高级光能
你这int行？
0
新手光能
long long啊!大哥！
0
高级守护
实在不行用unsigned long long
0
新手守护
不会
0
初级天翼
十年OI一场空，不开________见祖宗
