Cod sursa(job #1368588)

Utilizator vlady1997Vlad Bucur vlady1997 Data 2 martie 2015 18:43:17
Problema Ubuntzei Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#define INF 1000000
using namespace std;
struct oras
{
    vector <int> nod, cost;
};
oras g[2001];
queue <int> Q;
int a[2001], q[2001], Cost[2001], nr=0;
bool sel[2001], ok[2001], used[2001];
void dfs (int x)
{
    int i; sel[x]=true; q[++nr]=x;
    for (i=0; i<g[x].nod.size(); i++)
    {
        if (!sel[g[x].nod[i]])
        {
            dfs(g[x].nod[i]);
        }
    }
}
void bellmanford(int x, int n)
{
    int i, nod;
    while (!Q.empty()) Q.pop();
    memset(Cost,0,sizeof(Cost));
    memset(used,0,sizeof(used));
    Q.push(x); used[1]=true;
    for (i=1; i<=n; i++) if (i!=x) Cost[i]=INF;
    while (!Q.empty())
    {
        nod=Q.front(); Q.pop();
        used[nod]=false;
        for (i=0; i<g[nod].nod.size(); i++)
        {
            if (Cost[nod]+g[nod].cost[i]<Cost[g[nod].nod[i]])
            {
                Cost[g[nod].nod[i]]=Cost[nod]+g[nod].cost[i];
                if (!used[g[nod].nod[i]])
                {
                    used[g[nod].nod[i]]=true;
                    Q.push(g[nod].nod[i]);
                }
            }
        }
    }
}
int main()
{
    int n, m, k, i, x, y, z, sum=0;
    freopen("ubuntzei.in","r",stdin);
    freopen("ubuntzei.out","w",stdout);
    scanf("%d%d%d",&n,&m,&k);
    for (i=1; i<=k; i++) {scanf("%d",&a[i]); ok[a[i]]=true;}
    for (i=1; i<=m; i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        g[x].nod.push_back(y);
        g[y].nod.push_back(x);
        g[x].cost.push_back(z);
        g[y].cost.push_back(z);
    }
    dfs(1); x=1;
    for (i=2; i<=n; i++)
    {
        if (ok[q[i]]==true)
        {
            bellmanford(q[x],n);
            sum+=Cost[q[i]];
            x=i;
        }
    }
    bellmanford(q[x],n);
    if (ok[n]==false) sum+=Cost[n];
    printf("%d",sum);
    return 0;
}