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 13408100238 at 2014-08-16 10:59:39 on Problem 3255
```#include"iostream"
#include"cstdio"
#include"cstring"
#include"algorithm"
#include"cstdlib"
#include"queue"
#include"vector"
using namespace std;
const int inf=0x7fffffff;
const int ms=100001;
struct edge
{
//int from;
int to;
int cost;
};
typedef pair<int,int> P;
int main()
{
int i,j,N,R,ans,a,b,w;
scanf("%d%d",&N,&R);
vector<edge> vec[N+1];
for(i=1;i<=R;i++)
{
scanf("%d%d%d",&a,&b,&w);
edge e;
e.to=b;
e.cost=w;
//vec[a].push_back(edge{b,w});  有警告
vec[a].push_back(e);
e.to=a;
vec[b].push_back(e);
}
int dist[N+1],dist2[N+1];
priority_queue<P,vector<P>,greater<P> > que;
fill(dist,dist+N+1,inf);
fill(dist2,dist2+N+1,inf);
dist[1]=0;
que.push(P(0,1));
while(!que.empty())
{
P p=que.top();
que.pop();
int v=p.second;
int d=p.first;
if(dist2[v]<d)
continue;
for(i=0;i<vec[v].size();i++)
{
edge &e=vec[v][i];
int d2=d+e.cost;
if(dist[e.to]>d2)
{
swap(dist[e.to],d2);
que.push(P(dist[e.to],e.to));
}
if(dist2[e.to]>d2&&dist[e.to]<d2)
{
dist2[e.to]=d2;
que.push(P(dist2[e.to],e.to));
}
}
}
//printf("%d\n",dist2[N]);
cout<<dist2[N]<<endl;
return 0;
}```

Followed by: