Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

大佬们,超内存怎么办

Posted by 101SS at 2019-03-27 11:27:59 on Problem 3169
#include <iostream>
#include<set>
#include<cmath>
#include<queue>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<memory.h>
#define INF 0x3f3f3f3f
using namespace std;
int n,ml,md;
int d[1005];//最大距离
vector<int> g[1005];
vector<int> cost[1005];
int v1,v2,c;
typedef pair<int,int> P;
struct cmp{
	bool operator()(P p1,P p2)
	{
		return p1.first<p2.first;
	}
};
priority_queue<P,vector<P>,cmp> q;
int _need[1005];
void dirj()
{
	q.push(P(1,0));//先顶点后最大距离
	d[1]=0;
	while(!q.empty())
	{
		P p=q.top();
		int u=p.first;
		
		q.pop();
		for(int j=0;j<g[u].size();j++)
		{
			int v=g[u][j];
			
			if(d[v]<d[u]+cost[u][j])
			{
				d[v]=d[u]+cost[u][j];
				q.push(P(v,d[v]));
			}
		}
		
	}
	printf("%d\n",d[n]);
}
int main()
{
   while(scanf("%d %d %d",&n,&ml,&md)!=EOF)
   {
	   for(int i=1;i<=n;i++) {d[i]=0;g[i].clear();cost[i].clear();}
	  memset(_need,1,sizeof(int)*1005);
	   for(int i=0;i<ml;i++)
	   {
		   scanf("%d %d %d",&v1,&v2,&c);
		   g[v1].push_back(v2);
		   cost[v1].push_back(c);
		  
	   }
	   for(int i=0;i<md;i++)
	   {
		   cin>>v1>>v2>>c;
		   g[v2].push_back(v1);
		   cost[v2].push_back(0-c);
		   
	   }
	   
	   dirj();
   }
   return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator