逆天代码求条
查看原帖
逆天代码求条
716099
lovely_hyzhuo楼主2024/1/12 18:07

这个代码感觉没问题啊

#include<bits/stdc++.h>
using namespace std;
const long long INF=(1ll<<31)-1;
int head[1000010],tot;
struct node
{
    int to,dis,next;
}edge[10000010];
int n,m,s;
long long d[6][1000010];
bool vis[1000010];
long long ans=11451419181;
int a[6];
int v[6];
void dfs(long long sum,int q,int last)
{
	if(q==6)
	{
		ans=min(ans,sum);
		return;
	}
	for(int i=1;i<=5;i++)
	{
		if(v[i]==0)
		{
			v[i]=1;
			dfs(sum+d[last][a[i]],q+1,i);
			v[i]=0;
		}
	}
}
void add(int from,int to,int dis)
{
    edge[++tot].to=to;
	edge[tot].dis=dis;
    edge[tot].next=head[from];
    head[from]=tot;
}
void dijstra(int s,int t)
{
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
    {
    	d[s][i]=INF;
	} 
    d[s][t]=0;
    priority_queue<pair<long long ,int> >q;
    q.push(make_pair(0,s));
    while(q.size())
    {
        int x=q.top().second;
		q.pop();
        if(vis[x])
		{
			continue;
		}
        vis[x]=1;
        for(int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to,dis=edge[i].dis;
            if(d[s][y]>d[s][x]+dis)
            {
                d[s][y]=d[s][x]+dis;
                q.push(make_pair(-d[s][y],y));
            }           
        }
    }   
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=5;i++)
    	cin>>a[i];
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
    }
    dijstra(0,1);
    for(int i=1;i<=n;i++)
    	dijstra(i,a[i]);
    dfs(0,1,0);
    cout<<ans;
    return 0;
}

您可以试着跑一下样例看下它哪里逆天了

2024/1/12 18:07
加载中...