1 条题解

  • 0
    @ 2022-11-13 16:23:59
    /*****************************************
    Note:
    ******************************************/
    #include <queue>
    #include <set>
    #include <math.h>
    #include <stack>
    #include <stdio.h>
    #include <iostream>
    #include <vector>
    #include <iomanip>
    #include <string.h>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    #define LL long long
    const int N = 1e6 + 10;
    const int INF = 0x3f3f3f3f;
    int n,m,ans,i,j,k,x;
    int head[N],ne[N],to[N],dis[N],w[N],id,maxn;
    bool vis[N];
    void add(int x,int y,int z)
    {
    	to[++id]=y,w[id]=z,ne[id]=head[x],head[x]=id;
    }
    struct node{
    	int id,num;
    	bool operator<(const node &a)const
    	{
    		return num>a.num;
    	}
    };
    void dij()
    {
    	priority_queue<node>p;
    	p.push((node){x,0});
    	p.push((node){x+n,0});
    	dis[x]=dis[n+x]=0;
    	while(!p.empty())
    	{
    		node t=p.top();
    		p.pop();
    		if(vis[t.id]||dis[t.id]!=t.num)
    			continue;
    		vis[t.id]=1;
    		for(int i=head[t.id];i;i=ne[i])
    		{
    			int v=to[i];
    			if(!vis[v]&&dis[v]>dis[t.id]+w[i])
    			{
    				dis[v]=dis[t.id]+w[i];
    				p.push((node){v,dis[v]});
    			}
    		}
    	 } 
    }
    int main()
    {
    	memset(dis,0x3f,sizeof vis);
    	cin>>n>>m>>x;
    	for(int i=1;i<=m;++i)
    	{
    		int x,y,z;
    		cin>>x>>y>>z;
    		add(x,y,z);
    		add(y+n,x+n,z);
    	}
    	dij();
    	for(int i=1;i<=n;++i)
    		maxn=max(maxn,dis[i]+dis[i+n]);
    	cout<<maxn;
    	return 0;
    }
    
    • 1

    信息

    ID
    412
    时间
    1000ms
    内存
    512MiB
    难度
    4
    标签
    递交数
    32
    已通过
    19
    上传者