fork(2) download

copy

#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <stack>
#include <queue>
#include <climits>
 
using namespace std;
 
#define ll long long 
#define pb push_back
#define mp make_pair
 
vector<pair<int,int> > mygraph[100001];
int dist[100001];
 
void shortestpath(int n, int s);
class heapnode
{
public:
	int vertex;
	int key;
};
 
bool compare( heapnode &a, heapnode &b )
{
	if (a.key < b.key)
		return true;
	return false;
}
 
int main (void)
{
	int t,i,j;
	for ( i = 0; i < 100001; i++ )
		dist[i] = -1;
	int a,b,c;
	int foo,n,m,s,e;
	cin>>t;
	while (t != 0)
	{
		cin>>n>>m>>s>>e;
		foo = m;
		while (foo != 0)
		{
			cin>>a>>b>>c;
			mygraph[a].pb(mp(b,c));
			mygraph[b].pb(mp(a,c));
			foo--;
		}
		shortestpath(n,s);
		if (dist[e] == -1)
			cout<<"NONE\n";
		else
			cout<<dist[e]<<"\n";
		t--;
	}
	return 0;
}
 
void shortestpath(int n, int s)
{
	vector<heapnode> myvec;
	myvec.resize(n);
	int i,j,val,weight;
	for ( i = 1; i <= n; i++ )
	{
		myvec[i].vertex = i;
		myvec[i].key = INT_MAX;
	}
	myvec[s].key = 0;
	bool visited[n+1];
	for ( i = 1; i <= n; i++)
		visited[i] = false;
	make_heap(myvec.begin(),myvec.end(),compare);
	vector<int> processedver;
	while (processedver.size() != n)
	{
		heapnode obj = myvec.front();
		pop_heap(myvec.begin(),myvec.end());
		myvec.pop_back();
		processedver.pb(obj.vertex);
		dist[obj.vertex] = obj.key;
		int u = obj.vertex;
		visited[u] = true;
		auto it = mygraph[u].begin();
		while (it != mygraph[u].end())
		{
			for (int j = 1; j <= n; j++)
			{
				if (it->first == j)
				{
					val = j;
					weight = it->second;
					break;
				}		
			}
			if (visited[val] != true && myvec[val].key > (dist[u]+weight))
			{
				myvec[val].key = dist[u]+weight;
			}
			make_heap(myvec.begin(),myvec.end(),compare);
			it++;
		}
	}
}
 
 
 

In file included from /usr/include/c++/5/bits/stl_algobase.h:71:0,
                 from /usr/include/c++/5/bits/char_traits.h:39,
                 from /usr/include/c++/5/ios:40,
                 from /usr/include/c++/5/ostream:38,
                 from /usr/include/c++/5/iostream:39,
                 from prog.cpp:1:
/usr/include/c++/5/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_less_iter::operator()(_Iterator1, _Iterator2) const [with _Iterator1 = __gnu_cxx::__normal_iterator<heapnode*, std::vector<heapnode> >; _Iterator2 = __gnu_cxx::__normal_iterator<heapnode*, std::vector<heapnode> >]':
/usr/include/c++/5/bits/stl_heap.h:215:14:   required from 'void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<heapnode*, std::vector<heapnode> >; _Distance = int; _Tp = heapnode; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/5/bits/stl_heap.h:245:25:   required from 'void std::__pop_heap(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<heapnode*, std::vector<heapnode> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/5/bits/stl_heap.h:279:19:   required from 'void std::pop_heap(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<heapnode*, std::vector<heapnode> >]'
prog.cpp:83:37:   required from here
/usr/include/c++/5/bits/predefined_ops.h:43:23: error: no match for 'operator<' (operand types are 'heapnode' and 'heapnode')
       { return *__it1 < *__it2; }
                       ^
In file included from /usr/include/c++/5/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/5/bits/char_traits.h:39,
                 from /usr/include/c++/5/ios:40,
                 from /usr/include/c++/5/ostream:38,
                 from /usr/include/c++/5/iostream:39,
                 from prog.cpp:1:
/usr/include/c++/5/bits/stl_iterator.h:849:5: note: candidate: template<class _IteratorL, class _IteratorR, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_IteratorL, _Container>&, const __gnu_cxx::__normal_iterator<_IteratorR, _Container>&)
     operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
     ^
/usr/include/c++/5/bits/stl_iterator.h:849:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/5/bits/stl_algobase.h:71:0,
                 from /usr/include/c++/5/bits/char_traits.h:39,
                 from /usr/include/c++/5/ios:40,
                 from /usr/include/c++/5/ostream:38,
                 from /usr/include/c++/5/iostream:39,
                 from prog.cpp:1:
/usr/include/c++/5/bits/predefined_ops.h:43:23: note:   'heapnode' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
       { return *__it1 < *__it2; }
                       ^
In file included from /usr/include/c++/5/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/5/bits/char_traits.h:39,
                 from /usr/include/c++/5/ios:40,
                 from /usr/include/c++/5/ostream:38,
                 from /usr/include/c++/5/iostream:39,
                 from prog.cpp:1:
/usr/include/c++/5/bits/stl_iterator.h:856:5: note: candidate: template<class _Iterator, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_Iterator, _Container>&, const __gnu_cxx::__normal_iterator<_Iterator, _Container>&)
     operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
     ^
/usr/include/c++/5/bits/stl_iterator.h:856:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/5/bits/stl_algobase.h:71:0,
                 from /usr/include/c++/5/bits/char_traits.h:39,
                 from /usr/include/c++/5/ios:40,
                 from /usr/include/c++/5/ostream:38,
                 from /usr/include/c++/5/iostream:39,
                 from prog.cpp:1:
/usr/include/c++/5/bits/predefined_ops.h:43:23: note:   'heapnode' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
       { return *__it1 < *__it2; }
                       ^

Standard output is empty