不是洛谷的题
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int N=85;
struct edge{
int v,w;
};
vector<edge>e[N];
int n,s,d[N],vis[N];
void hdckstra(int s){
memset(d,0x3f,sizeof(d));
d[s]=0;
priority_queue<pair<int,int> >q;
q.push({0,s});
while(q.size()){
auto t=q.top();q.pop();
int u=t.second;
if(vis[u]) continue;
vis[u]=1;
for(auto hdc:e[u]){
int v=hdc.v,w=hdc.w;
if(d[v]>d[u]+w){
d[v]=d[u]+w;
q.push({-d[v],v});
}
}
}
}
int main(){
scanf("%d%d",&n,&s);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
string a;
cin>>a;
int t=0,la=a.size(),t1=1;
if(a[0]=='-'&&la==1||i==j) continue;
for(int i=0;i<la;i++){
if(a[i]=='-'&&i==0){
t1=0;
continue;
}
t=t*10+(a[i]-'0');
}
if(t1){
e[i].push_back({j,t});
}else{
e[i].push_back({j,-t});
}
}
}
hdckstra(s);
for(int i=1;i<=n;i++){
if(i==s) continue;
printf("(%d -> %d) = %d\n",s,i,d[i]);
}
return 0;
}