70分求助
查看原帖
70分求助
981005
KipperLee楼主2024/3/23 14:08

70分,WA了三个点,代码如下:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

const int N = 2e4 + 5;
int cnt = 0, hd[N], dis[N];
bool vis[N];

struct node
{
    int d;
    int pos;
    
    bool operator < (const node &p) const
    {
        return d > p.d;
    }
};

struct edge
{
    int to;
	int nxt;
} e[50005];

priority_queue<node> q;

void insert(int u, int v)
{
	e[++cnt] = {v, hd[u]};
	hd[u] = cnt;
}

void dijkstra(int s)
{
    dis[s] = 0;
    q.push({0, s});
    
    while (!q.empty())
    {
        node head = q.top();
		int x = head.pos;
		
        q.pop();
        
        if (vis[x])
		{
			continue;
		}
		
        vis[x] = true;
        
        for (int i = hd[x]; i != 0; i = e[i].nxt)
        {
            int y = e[i].to;
            
            if (dis[y] > dis[x] + 1)
            {
                dis[y] = dis[x] + 1;
                
                if (!vis[y])
                {
                    q.push({dis[y], y});
                }
            }
        }
    }
}


int main()
{
	int n, m;
    cin >> n >> m;
    
    memset(dis, 999999, sizeof(dis));
    
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        insert(u, v);
        insert(v, u);
    }
    
    dijkstra(1);
    
    int ans = *max_element(dis + 1, dis + n + 1), tot = 0;
    
    cout << max_element(dis + 1, dis + n + 1) - dis << " " << ans << " ";
    
    for (int i = 1; i <= n; i++)
    {
    	tot += (dis[i] == ans);
	}
	
	cout << tot;
	
    return 0;
}
2024/3/23 14:08
加载中...