pku3159Candies(spfa差分约束)
| 6737446 | Xredman | 3159 | Accepted | 2092K | 735MS | C++ | 1263B | 2010-04-13 14:35:15 |
参考http://hi.baidu.com/qqmxiaoc/blog/item/e289c41ee4ba0103304e1597.html
#include <iostream>
#include <stack>
#include <cstdio>
#include <cstring>
#include <climits>
using namespace std;
const int MAXV = 30002;
const int MAXE = 150002;
#define INF INT_MAX
int pnt[MAXE], cost[MAXE], next[MAXE];
int head[MAXV];
int dist[MAXV];
bool Visited[MAXV];
int cnt;
int n, m;
void addEdge(int u, int v, int c)
{
pnt[cnt] = v;//终点
cost[cnt] = c;
next[cnt] = head[u];
head[u] = cnt++;
}
bool relax(int u, int v, int c)
{
if(dist[u] != INF && dist[v] > dist[u] + c)
{
dist[v] = dist[u] + c;
return true;
}
return false;
}
int spfa(int src)
{
int i;
int u, v;
for(i = 1; i <= n; i++)
{
dist[i] = INF;
Visited[i] = false;
}
dist[src] = 0;
stack<int> S;
S.push(src);
Visited[src] = true;
while(!S.empty())
{
u = S.top();
S.pop();
Visited[u] = false;
for(i = head[u]; i != -1; i = next[i])
{
v = pnt[i];
if(relax(u, v, cost[i]) && !Visited[v])
{
S.push(v);
Visited[v] = true;
}
}
}
return dist[n];
}
int main()
{
int a, b, d;
while(cin>>n>>m)
{
cnt = 0;
memset(head, -1, sizeof(head));
while(m--)
{
scanf("%d%d%d", &a, &b, &d);
addEdge(a, b, d);
}
cout<<spfa(1)<<endl;;
}
return 0;
}
Sep 25, 2022 07:02:35 PM
Most of the candidates show interest to download NCERT English Sample Paper 2023 Class 11 to gain high score in different types of exams such as Term-1, Term-2. Most of the candidates show interest to download NCERT English Sample Paper 2023 Class 11 to gain high score in different types of exams such as Term-1, Term-2 and other types of exams. Basically for 11th standard students these exams are conducting by the Board of NCERT to check the students individual abilities. and other types of exams. NCERT English Sample Paper Class 11 Basically for 11th standard students these exams are conducting by the Board of NCERT to check the students individual abilities.
Aug 31, 2023 09:09:15 PM
Uttar Pradesh Madhyamik Shiksha Parishad (UPMSP) is the Uttar Pradesh State Government Administered Autonomous Examining Authority for the 10th Standard Examination of Uttar Pradesh, headquartered in Prayagraj, India, UP Board 10th Blueprint 2024 UP Board Every Year Conducted 10th Class Public Exam Month of March. UPMSP Every year for Announced 10th Class Blueprint in before the UP Board Public Exam, UP Board 10th Blueprint 2024 helps Students to Understand the type of Questions in the Public Exam, However, Students must note that the Marks Distribution are only for Reference and the Weightage Distribution in the Exam are Different.
Jan 25, 2024 07:03:14 AM
Pavzi website is a multiple Niche or category website which will ensure to provide information and resources on each and every topic. Some of the evergreen topics you will see on our website are Career, Job Recruitment, Educational, Technology, Reviews and others. pavzi.com We are targeting mostly so it is true that Tech, Finance, and Product Reviews. The only reason we have started this website is to make this site the need for your daily search use.