/* Bismillahir Rahmanir Rahim
Solution-Using Dijkstra.
Calculate shortest path and second shortest path for each node
*/
#include<bits/stdc++.h>
#define fi(n, m) for(int i=n; i<=m; i++)
#define ll long long
using namespace std;
vector<ll>vt[5009], cost[5009];
ll n, en, d1[5009], d2[5009], sz; //d2[]=second shortest, d1[]=shortest
struct node{
ll u, w;
node(ll a, ll b){
u=a, w=b;
}
bool operator < (const node & p)const{
return p.w<w;
}
};
void dijkstra(int st){
priority_queue<node>q;
q.push(node(st, 0));
fi(1, n){d1[i]=30000000, d2[i]=30000000;}
d1[st]=0;
while(!q.empty()){
node top=q.top();
q.pop();
int u=top.u;
sz=vt[u].size();
fi(0, sz-1){
int v=vt[u][i];
int uu=cost[u][i]; // mind it
if(d1[u]+uu<d1[v]){
ll temp=d1[v];
d1[v]=d1[u]+uu;
d2[v]=min(temp, min(d2[v], min(d2[u]+uu, d1[u]+3*uu)));
q.push(node(v, d1[v]+d2[v]));
}
else if(d1[u]+uu<d2[v] && (d1[u]+uu)>d1[v]){
d2[v]=d1[u]+uu;
}
else{
d2[v]=min(d2[v], min(d2[u]+uu, d1[u]+3*uu));
}
}
}
}
int main(){
int t, cs=1, st, e, u, v, w, nn, ans;
cin>>t;
while(t--){
cin>>n>>e;
fi(1, e){
cin>>u>>v>>w;
vt[u].push_back(v);
vt[v].push_back(u);
cost[u].push_back(w);
cost[v].push_back(w);
}
ll back=100000009; // Its for a special case, given bellow
fi(0, vt[1].size()-1){
back=min(back, 2*cost[1][i]);
}
dijkstra(1);
back=d1[n]+back;
cout<<"Case "<<cs++<<": "<<min(back, d2[n])<<endl;
fi(0, n){
vt[i].clear(); cost[i].clear();
}
}
return 0;
}
/* Special Case
Input:
1
4 5
1 2 3
2 3 7
3 4 4
1 2 4
4 1 4
Output:
Case 1: 10
*/
|
Showing posts with label Dijkstra. Show all posts
Showing posts with label Dijkstra. Show all posts
Saturday, March 18, 2017
Solution of Light OJ 1099 - Not the Best
Saturday, February 25, 2017
Solution of Light OJ 1174-Commandos
/* بسم الله الرØمن الرØيم
Solution - using "Dijkstra".
Calculate the shortest path for all node from both starting
node and ending node then mx=max(mx, (d1[i]+d2[i]))
*/
#include<bits/stdc++.h>
#define fi(n, m) for(int i=n; i<=m; i++)
#define fd(n, m) for(int i=n; i>=m; i--)
using namespace std;
vector<int>vt[101], cost[101];
int d1[101], d2[101], n;
struct node{
int u, w;
node(int a, int b){
u=a, w=b;
}
bool operator < (const node & p)const{
return p.w<w;
}
};
void dijkstra(int st){
priority_queue<node>q;
fi(0, n-1)d1[i]=100009;
d1[st]=0;
q.push(node(st, 0));
while(!q.empty()){
node top=q.top();
q.pop();
int u=top.u;
int sz=vt[u].size();
fi(0, sz-1){
int v=vt[u][i];
if(d1[u]+cost[u][i]<d1[v]){
d1[v]=d1[u]+cost[u][i];
q.push(node(v, d1[v]));
}
}
}
}
void ddijkstra(int st){
priority_queue<node>q;
fi(0, n-1) d2[i]=100009;
d2[st]=0;
q.push(node(st, 0));
while(!q.empty()){
node top=q.top();
q.pop();
int u=top.u;
int sz=vt[u].size();
fi(0, sz-1){
int v=vt[u][i];
if(d2[u]+cost[u][i]<d2[v]){
d2[v]=d2[u]+cost[u][i];
q.push(node(v, d2[v]));
}
}
}
}
int main(){
int t, u, v, e, st, cs=1, en, a1, a2, mx;
cin>>t;
while(t--){
mx=0;
cin>>n>>e;
fi(0, e-1){
cin>>u>>v;
vt[u].push_back(v);
vt[v].push_back(u);
cost[u].push_back(1);
cost[v].push_back(1);
}
cin>>st>>en;
/* input end */
dijkstra(st);
ddijkstra(en);
fi(0, n-1) mx=max(mx, (d1[i]+d2[i]));
cout<<"Case "<<cs++<<": "<<mx<<endl;
fi(0, n-1){
vt[i].clear();
cost[i].clear();
}
}
return 0;
}
|
Thursday, February 23, 2017
Solution of Light OJ 1019 - Brush (V)
/* Bismillahir Rahmanir Rahim
Solution-Using Dijkstra algorithm
*/
#include<bits/stdc++.h>
#define fi(n, m) for(int i=n; i<=m; i++)
#define fd(n, m) for(int i=n; i>=m; i--)
using namespace std;
vector<int>vt[109], cost[109];
int dis[109], n;
struct node{
int u, w;
node(int a, int b){
u=a, w=b;
}
bool operator < (const node & p)const{
return p.w<w;
}
};
void dijkstra(int st){
priority_queue<node>q;
fi(0, n)dis[i]=1000001;
dis[st]=0;
q.push(node(st, 0));
while(!q.empty()){
node top=q.top();
q.pop();
int u=top.u;
int sz=vt[u].size();
fi(0, sz-1){
int v=vt[u][i];
if(dis[u]+cost[u][i]<dis[v]){
dis[v]=dis[u]+cost[u][i];
q.push(node(v, dis[v]));
}
}
}
}
int main(){
int t, cs=1, e, u, v, w;
cin>>t;
while(t--){
cin>>n>>e;
fi(0, e-1){
cin>>u>>v>>w;
vt[u].push_back(v);
vt[v].push_back(u);
cost[u].push_back(w);
cost[v].push_back(w);
}
dijkstra(1);
cout<<"Case "<<cs++<<": ";
if(dis[n]==1000001)cout<<"Impossible"<<endl;
else cout<<dis[n]<<endl;
fi(0, n){
vt[i].clear();
cost[i].clear();
}
}
return 0;
}
|
Solution of Light OJ 1002 - Country Roads
/* Bismillahir Rahmanir Rahim
Solution using Dijkstra algorithm.
*/
#include<bits/stdc++.h>
#define fi(n, m) for(int i=n; i<=m; i++)
#define fd(n, m) for(int i=n; i>=m; i--)
using namespace std;
vector<int>vt[1009], cost[1009];
int dis[1009], n;
struct node{
int u, w;
node(int a, int b){
u=a, w=b;
}
bool operator < (const node & p)const{
return p.w<w;
}
};
void dijkstra(int st){
priority_queue<node>q;
fi(0, n)dis[i]=20001;
dis[st]=0;
q.push(node(st, 0));
while(!q.empty()){
node top=q.top();
q.pop();
int u=top.u;
int sz=vt[u].size();
fi(0, sz-1){
int v=vt[u][i];
int temp=max(dis[u], cost[u][i]);
if(temp<dis[v]){
dis[v]=temp;
q.push(node(v, dis[v]));
}
}
}
}
int main(){
int e, u, v, w, m, t, cs=1;
cin>>t;
while(t--){
cin>>n>>e;
fi(0, e-1){
cin>>u>>v>>w;
vt[u].push_back(v);
vt[v].push_back(u);
cost[u].push_back(w);
cost[v].push_back(w);
}
cin>>m;
dijkstra(m);
cout<<"Case "<<cs++<<":"<<endl;
fi(0, n-1){
if(dis[i]==20001)cout<<"Impossible"<<endl;
else cout<<dis[i]<<endl;
}
fi(0, n-1){
vt[i].clear();
cost[i].clear();
}
}
return 0;
}
|
Subscribe to:
Posts (Atom)