Pagini recente » Cod sursa (job #1884025) | 1908 | Cod sursa (job #1322948) | Cod sursa (job #1521289) | Cod sursa (job #1648546)
#include<iostream>
#include<fstream>
using namespace std;
ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");
int a[2000][2000];
int t[2000],loc[2000],d[2000],h[2000];
int n,m,k,c=0;
void cit()
{
f>>n>>m>>k;
if(k!=0)
for(int i=1;i<=k;i++)
f>>loc[i];
int x,y,z;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i==j) a[i][j] = 0;
else a[i][j] = 10000;
for(int i = 1 ;i <= m; i++)
{
f >> x >> y >> z;
a[x][y] = z;
a[y][x] = z;
}
}
void dijkstra()
{
int ok=1,k,v[2000],mn;
for(int i = 1; i <= n; i++)
{
v[i] = 0;
t[i] = 1;
d[i] = a[1][i];
}
v[1] = 1;
t[1] = 0;
while(ok == 1)
{
mn = 10000;
for(int i = 1; i <= n; i++)
if(v[i]==0 and mn > d[i])
{
mn = d[i];
k = i;
}
if(mn != 10000)
{
v[k] = 1;
h[++c] = k;
for(int i=1;i<=n;i++)
if(v[i] == 0 and d[i] > d[k] + a[k][i])
{
t[i] = k;
d[i] = d[k] + a[k][i];
}
}
else ok = 0;
}
}
int main()
{
cit();
h[1] = 1;
c++;
dijkstra();v[1] = 1;
int s=0;
for(int i=1;i<=n;i++)
s += d[i];
g<<s-1;
}