UVA 558 - Wormholes

#include
#define sf scanf
#define pf printf
#define inf 1e18
#define INF 1000000000
#define MAX_N 5001
#define MAX_E 25000001
using namespace std;
typedef long long lld;

int v, e;

int dist[MAX_N];
struct Edge
{
    int x, y, weight;
    Edge(int _x, int _y, int _weight){
    x = _x;
    y = _y;
    weight = _weight;
    }
};
vector E;

int BellmanFord(int source)
{
    for (int i=0;i    {
        if (i == source) dist[i]=0;
        else dist[i] = INF;
    }
    bool done = false;
    for (int i=0;!done&&i    {
        done = true;
        for (int j=0;j        {
            int so = E[j].x;
            int de = E[j].y;
            if (dist[so] + E[j].weight < dist[de])
            {
                dist[de] = dist[so] + E[j].weight;
                done=false;
            }
        }
    }
    if (!done) return -1;
    return 0;
}

int main()
{
int t;
cin >> t;
while(t--){
E.clear();
    v  , e;
    cin >> v >> e;
    for(int i=0; i    int u , v , w;
    cin >> u >> v >> w;
    E.push_back(Edge(u,v,w));
    }
    BellmanFord(0) == -1 ? cout<<"possible\n":cout<<"not possible\n";
}
 
    return 0;

}

UVA 10986 - Sending email

#include <bits/stdc++.h>
#define sf scanf
#define pf printf
#define inf 1e18
#define MAX 1000000000
using namespace std;
struct Node{
int at , cost;
Node(int _at, int _cost){
at = _at;
cost = _cost;
}
};
bool operator<(Node A , Node B){
return A.cost > B.cost;
}
struct Edge{
int v, w;
Edge(int _v, int _w){
v = _v;
w = _w;
}
};
vector <Edge> adj[20000+1];
priority_queue<Node>PQ;
int dist[20000+1];
int n;

void dijkstra(int s){
for(int i=0; i<=n; i++){
dist[i] = MAX;
}
dist[s] = 0;
PQ.push(Node(s,0));

while(!PQ.empty()){
Node u = PQ.top();
PQ.pop();
if(u.cost != dist[u.at]){
continue;
}
for(Edge e: adj[u.at]){
if(dist[e.v] > u.cost + e.w){
dist[e.v] = u.cost + e.w;
PQ.push(Node(e.v, dist[e.v]));
}
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
int t,kase=0;
cin >> t;
while(t--){
memset(adj,0,sizeof adj);
while(!PQ.empty())PQ.pop();
  int edges , s , t;
  cin >> n >> edges >> s >>t;
  for(int i=0; i<edges; i++){
  int u , v , w;
  cin >>u >> v >> w;
  adj[u].push_back(Edge(v,w));
  adj[v].push_back(Edge(u,w));
  }
  dijkstra(s);
  if(dist[t] == MAX)cout <<"Case #"<<++kase<<": unreachable\n";
  else cout <<"Case #"<<++kase<<": "<<dist[t]<<'\n';
}



return 0;
}

UVA 762 - We Ship Cheap

#include <bits/stdc++.h>
#define sf scanf
#define pf printf
using namespace std;
map<string, bool>visited;
void bfs(string start , string end , map<string , vector<string> >mp)
{
vector<pair<string, string> >vp;
queue<string>q;
q.push(start);
visited[start] = true;
bool flag = false;
while(!q.empty()){
string top = q.front();
q.pop();
for(int i=0; i<mp[top].size(); i++){
if(!visited[mp[top][i]]){
visited[mp[top][i]] = true;
if(mp[top][i] != end){
vp.push_back(make_pair(top , mp[top][i]));
q.push(mp[top][i]);
}else if(mp[top][i] == end){
flag = true;
vp.push_back(make_pair(top , mp[top][i]));
break;
}
}
}
if(flag)break;
}
if(!flag && q.empty())cout << "No route\n";
else{
for(int i=0; i<vp.size(); i++)
cout << vp[i].first<< ' '<<vp[i].second<<'\n';
}

}
int main()
{
ios_base::sync_with_stdio(0);
int t;
bool first = true;
while(cin >> t){
if(!first)cout <<'\n';
first = false;
map<string , vector<string> > mp;
visited.clear();
while(t--){
string u , v;
cin >> u >> v;
mp[u].push_back(v);
mp[v].push_back(u);
}
string start, end;
cin >> start >> end;
bfs(start , end , mp);
}
}

UVA 336 - A Node Too Far

#include <bits/stdc++.h>
#define sf scanf
#define pf printf
using namespace std;
map<int, int>visited;

void bfs(int start, map<int, vector<int> > graph)
{
queue<int>q;
q.push(start);
visited[start] = 0;
while(!q.empty()){
int top = q.front();
q.pop();
int size = graph[top].size();
for(int i=0; i<size; i++){
int n = graph[top][i];
if(!visited.count(n)){
visited[n]=visited[top]+1;
q.push(n);
}
}
}

}

int main()
{
ios_base::sync_with_stdio(0);
int nodes , a  , b , kase =0;
while(cin >> nodes && nodes){
map<int, vector<int> >graph;
for(int i=0; i<nodes; i++){
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
int ttl , start;
while(cin >> start >> ttl ){
if(start==0 && ttl ==0)break;
map<int, int>::const_iterator it;
visited.clear();
bfs(start , graph);
int cnt =0;
for(it = visited.begin(); it!=visited.end(); it++){
if((*it).second >ttl)cnt++;
}
cnt += graph.size()-visited.size();

cout << "Case "<<++kase << ": "<<cnt <<" nodes not reachable from node "<<start<<" with TTL = "<<ttl<<".\n";

}
}
}

UVA 280 - Vertex

#include<bits/stdc++.h>
using namespace std;
vector<int>adj[105];
bool vis[105];
void bfs(int s , int nodes)
{
    fill(vis,vis+nodes,false);
    queue<int>q;
    while(!q.empty())q.pop();
    q.push(s);
    while(!q.empty()){
        int fr = q.front();
        q.pop();
        for(int i = 0; i < adj[fr].size(); i++){
            if(!vis[adj[fr][i]]){
                vis[adj[fr][i]] = true;
                q.push(adj[fr][i]);
            }

        }

    }
    int cnt = 0;
    for(int i=0; i<nodes; i++){
        if(!vis[i])cnt++;
    }
    cout <<cnt;
    for(int i=0; i<nodes; i++){
        if(!vis[i])cout <<' '<<i+1;
    }
    cout << '\n';

}

int main()
{
    int nodes;
    while(cin >> nodes && nodes){

        memset(adj,0,sizeof adj);

        int i;
        while(cin >> i && i){
            int j;
            while( cin >> j && j){
                adj[i-1].push_back(j-1);
            }
        }
        int t;
        cin >> t;
        while(t--){
            int query;
            cin >> query;
            bfs(query-1 , nodes);
        }

    }

return 0;
}