3 条题解

  • -2
    @ 2023-8-21 17:22:50

    #include using namespace std; struct node{ int v,w; }; int dis[1000001];int n,m,s; int h[1000001]; vector a[1000001]; priority_queue<pair,vector<pair >,greater<pair > > q; void dij(int s){ memset(dis,0x3f,sizeof(dis)); dis[s]=0; q.push(make_pair(0,s)); while(!q.empty()){ int u=q.top().second; q.pop(); if(h[u])continue; h[u]=1; for(int i=0;idis[u]+w){ dis[v]=dis[u]+w; q.push(make_pair(dis[v],v)); } } } } int d[1000001]; queueqq; bool spfa(int u){ memset(dis,0x3f,sizeof(dis)); dis[u]=0; qq.push(u); d[u]++; while(!qq.empty()){ int u=qq.front(); qq.pop(); if(h[u])continue; h[u]=0; for(int i=0;idis[u]+w){ dis[v]=dis[u]+w; if(h[v]==0){ h[v]=1; qq.push(v); if(d[u]>=n) return 0; } } } } return 1; } int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    	int u,v,w;
    	cin>>u>>v>>w;
    	a[u].push_back(node{v,w});
    }
    for(int)
    spfa(1);
    
    return 0;
    

    }//必定对

    • -19
      @ 2023-8-21 17:21:59

      题目要自己思考

      • -19
        @ 2023-8-21 17:20:56

        想啥呢,自己做

        • 1

        信息

        ID
        480
        时间
        1000ms
        内存
        256MiB
        难度
        2
        标签
        递交数
        190
        已通过
        84
        上传者