求助!三个蛋
查看原帖
求助!三个蛋
89948
封禁用户楼主2018/8/8 10:23
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 500001;
const int MAXM = 10001;
struct Line{
	int p;
	int v;
	int next;
}line[MAXM]; 
struct Node{
	int dist;
	int inq;
}node[MAXN];

int lineh[MAXN];
int q[MAXN];
int n,m,d,MAX,maxh,ans,s;

void work() {
    int h = -1, t = 0;
    q[0] = s;
    while (h != t) {
        h = (h + 1) % MAXN;
        int now = q[h];
        node[now].inq = false;
        int i = lineh[now];
        while (i != 0) {
            int p = line[i].p;
            if (node[now].dist + line[i].v < node[p].dist) {
                node[p].dist = node[now].dist + line[i].v;
                if(node[p].dist > MAX){
                	MAX = node[p].dist;
                	maxh = now;
                	ans = 1;
                }
                if(node[p].dist == MAX){
                	ans++;
                }
                if(node[p].dist == MAX && now < maxh){
                	maxh = now;
                }
                if (!node[p].inq) {
                    t = (t + 1) % MAXN;
                    q[t] = p;
                    node[p].inq = true;
                }
            }
            i = line[i].next;
        }
    }
}
int main(){
	cin>>n>>m;
	for(int i = 1;i <= m; i++){
		cin>>line[i].p>>line[i].next;
		line[i].v = 1;
		lineh[line[i].p] = i;
	}
	for(int i = 1;i <= n; i++){
		node[i].dist = (1 << 31) - 1;
		node[i].inq = false;
	}
	node[s].dist = 0;
    node[s].inq = true;
    work();
    cout<<maxh<<" "<<MAX<<" "<<ans;
    printf("\n");
    return 0;
}
2018/8/8 10:23
加载中...