3222241_ac_1360ms_3352k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#define max 10001
using namespace std;
 
int INF = 2100000000;

int N, M, K;

struct Node
{
	int tar;
	int id;
	int value;
};

struct node
{
	int value;
	int tar;
 
	bool operator<(const node & x) const
	{
		if (value>x.value) return true;
		return false;
	}
};

priority_queue< node ,vector<node> > q;

bool used[max];

void dijk(int start,vector <Node> e [],int dis[])
{
	int i, j, k;

	while (!q.empty()) q.pop();
 
	for (i = 0; i < N; ++i) dis[i]=INF;
	memset(used,false,sizeof(used));
 
	node temp,temp2;
	temp.value=0;
	temp.tar=start;
	q.push(temp);
 
	while (!q.empty())
	{
		while (!q.empty() && used[q.top().tar]) q.pop();
		if (q.empty()) break;
		temp=q.top();
		q.pop();

		used[temp.tar]=true;
		dis[temp.tar]=temp.value;

		for (k=0;k<e[temp.tar].size();++k) 
		{
			j=e[temp.tar][k].tar;
			if (dis[temp.tar]+e[temp.tar][k].value< dis[j] && !used[j])
			{
				dis[j]=dis[temp.tar]+e[temp.tar][k].value;
				temp2.tar=j;
				temp2.value=dis[j];
				q.push(temp2);
			}
		}
	}
}

vector<Node> edge[max], Edge[max];
int dis[max], Dis[max];

void init()
{
	int i, j, k, l;
 
	scanf("%d%d%d",&N,&M,&K);
	for (i = 0; i < M; ++i)
	{
		scanf("%d%d%d",&j,&k,&l);
		Node t;
		j--;k--;
		t.tar = k;t.value = l;t.id = i+1;
		edge[j].push_back(t);
		t.tar = j;
		Edge[k].push_back(t);
	}
}

int main()
{
	int i, j;
	vector <int> ans;

	init();
	dijk(0,edge,dis);
	dijk(N-1,Edge,Dis);
	ans.clear();
	if(dis[N-1]==INF)
	{
		puts("0");
		return 0;
	}
	for(i = 0; i < N; i++)
	{
		if(dis[i]==INF)
			continue;
		for(j = 0; j < edge[i].size(); j++)
		{
			if(Dis[edge[i][j].tar]==INF)
				continue;
			if(dis[i]+Dis[edge[i][j].tar]+edge[i][j].value <= dis[N-1]+K)
			{
				ans.push_back(edge[i][j].id);
			}
		}
	}
	sort(ans.begin(),ans.end());
	printf("%d\n",ans.size());
	for(i = 0; i < ans.size(); i++)
	{
		printf("%d\n",ans[i]);
	}
	return 0;
}