样例过了,75分,求救
  • 板块学术版
  • 楼主peijun714
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/10/1 15:06
  • 上次更新2024/10/1 16:35:30
查看原帖
样例过了,75分,求救
1057373
peijun714楼主2024/10/1 15:06

不是洛谷的题

#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;
}
2024/10/1 15:06
加载中...