Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
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: