Dijkstra2

#include <fstream>
#include <cstdio>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>

using namespace std;
#define ii pair<int,int>
#define pb push_back
#define inf 1000000000
int n,e,source;
vector<ii> g[100000];
int dist[100000];
bool marked[100000];
ifstream fin("dijkstra2.in");
ofstream fout("dijkstra2.out");
void apply_dijkstra()
{
	set<ii > s;
	s.insert(ii(0,source));
	dist[source] = 0;marked[source] = 1;
	while(!s.empty())
	{
		ii p = *s.begin();
		s.erase(p);
		marked[p.second] = 2;
		for(unsigned i=0;i<g[p.second].size();i++)
			if(marked[g[p.second][i].second]==0)
			{
				s.insert(ii(dist[p.second]+g[p.second][i].first,g[p.second][i].second));
				marked[g[p.second][i].second] = 1;
				dist[g[p.second][i].second] = dist[p.second]+g[p.second][i].first;
			}
			else if(marked[g[p.second][i].second]==1 && dist[g[p.second][i].second] > dist[p.second]+g[p.second][i].first)
			{
				s.erase(ii(dist[g[p.second][i].second],g[p.second][i].second));
				s.insert(ii(dist[p.second]+g[p.second][i].first,g[p.second][i].second));
				dist[g[p.second][i].second] =  dist[p.second]+g[p.second][i].first;
			}
	}
	for(int i=1;i<=n;i++)
	{
		if(dist[i]==inf)
            fout<<-1<<' ';
        else
            fout<<dist[i]<<' ';
	}
}

int main()
{
	for(int i=0;i<100000;++i)
        dist[i]=inf;
	fin>>n>>e>>source;
	for(int i=0;i<e;i++)
	{
		int x,y,w;
		fin>>x>>y>>w;
		g[x].pb(ii(w,y)),g[y].pb(ii(w,x));
	}
	apply_dijkstra();
	return 0;
}