Pagini recente » oji2013 | Borderou de evaluare (job #1685775) | Borderou de evaluare (job #2040667) | Borderou de evaluare (job #172396) | Cod sursa (job #680194)
Cod sursa(job #680194)
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
#define MAX_N 2001
#define mp make_pair
#define INF 9999999
int n,m,k,prieteni[MAX_N],d[MAX_N],t[MAX_N];
vector<int> drum;
vector < pair<int,int> > gr[MAX_N];
void read(void)
{
freopen("ubuntzei.in","r",stdin);
int i,x,y,c;
scanf("%d %d %d",&n,&m,&k);
for(i=1; i<=k; i++)
scanf("%d",&prieteni[i]);
for(i=1; i<=m; i++)
{
scanf("%d %d %d",&x,&y,&c);
gr[x].push_back(mp(y,c));
gr[y].push_back(mp(x,c));
}
}
void bellman_ford(int start)
{
int i,x; queue<int> C;
vector < pair<int,int> > ::iterator it;
for(i=2; i<=n; i++)
d[i]=INF;
C.push(start);
while(!C.empty())
{
x=C.front();
C.pop();
for(it=gr[x].begin(); it!=gr[x].end(); it++)
if(d[it->first]>d[x]+it->second)
{
d[it->first]=d[x]+it->second;
t[it->first]=x;
C.push(it->first);
}
}
}
void build_path(int nod)
{
if(t[nod])
build_path(t[nod]);
drum.push_back(nod);
}
int solve_length()
{
int L=0;
vector<int> ::iterator i;
vector< pair<int,int> > ::iterator j;
for(i=drum.begin(); i!=drum.end(); i++)
if(*i!=drum.back())
{
for(j=gr[*i].begin(); j!=gr[*i].end(); j++)
if(j->first==*(i+1))
{
L+=j->second;
break;
}
}
return L;
}
void write(void)
{
freopen("ubuntzei.out","w",stdout);
printf("%d ",solve_length());
}
int main()
{
read();
bellman_ford(1);
build_path(n);
write();
return 0;
}