7.11
P2865:
#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>inline void read(T&x){
x=0;
char c;
int sign=1;
do{
c=getchar();
if(c=='-'){
sign=-1;
}
}while(!isdigit(c));
do{
x=x*10+c-'0';
c=getchar();
}while(isdigit(c));
x*=sign;
}
inline void write(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)write(x/10);
putchar(x%10+'0');
}
const int N=1e5+50,M=5e5+50;
int n,m,s;
int head[N],nxt[M],to[M],w[M],tot;
void add(int x,int y,int val){
to[tot]=y;
nxt[tot]=head[x];
w[tot]=val;
head[x]=tot++;
}
int d[2][N];
int vis[N];
priority_queue<pair<int,int> >q;
void spfa(int x){
memset(d,0x3f,sizeof(d));
d[0][s]=0;
q.push(make_pair(0,s));
while(!q.empty()){
int x=q.top().second;
q.pop();
for(int i=head[x];~i;i=nxt[i]){
if(d[0][to[i]]==d[0][x]+w[i]);
else if(d[0][to[i]]>d[0][x]+w[i]){
d[1][to[i]]=d[0][to[i]];
d[0][to[i]]=d[0][x]+w[i];
q.push(make_pair(-d[0][to[i]],to[i]));
}
else if(d[1][to[i]]>d[0][x]+w[i]){
d[1][to[i]]=d[0][x]+w[i];
q.push(make_pair(-d[1][to[i]],to[i]));
}
if(d[1][to[i]]>d[1][x]+w[i]){
d[1][to[i]]=d[1][x]+w[i];
q.push(make_pair(-d[1][to[i]],to[i]));
}
}
}
}
int x,y,r;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
memset(head,-1,sizeof(head));
read(n);
read(m);
s=1;
for(int i=1;i<=m;i++){
read(x);
read(y);
read(r);
add(x,y,r);
add(y,x,r);
}
spfa(s);
write(d[1][n]);
putchar('\n');
return 0;
}dijkstra:
#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>inline void read(T&x){
x=0;
char c;
int sign=1;
do{
c=getchar();
if(c=='-'){
sign=-1;
}
}while(!isdigit(c));
do{
x=x*10+c-'0';
c=getchar();
}while(isdigit(c));
x*=sign;
}
inline void write(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)write(x/10);
putchar(x%10+'0');
putchar(' ');
}
const int N=1e5+50,M=5e5+50;
int n,m,s;
int head[N],nxt[M],to[M],w[M],tot;
void add(int x,int y,int val){
to[tot]=y;
nxt[tot]=head[x];
w[tot]=val;
head[x]=tot++;
}
int d[N];
int vis[N];
priority_queue<pair<int,int> >q;
void dij(int x){
for(int i=0;i<=n;i++){
d[i]=INT_MAX;
}
d[s]=0;
q.push(make_pair(-d[s],s));
for(int t=1;t<n;t++){
while(vis[q.top().second]){
q.pop();
}
x=q.top().second;
q.pop();
vis[x]=1;
for(int i=head[x];~i;i=nxt[i]){
if(d[to[i]]>d[x]+w[i]){
d[to[i]]=d[x]+w[i];
q.push(make_pair(-d[to[i]],to[i]));
}
}
}
}
int x,y,r;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
memset(head,-1,sizeof(head));
read(n);
read(m);
read(s);
for(int i=1;i<=m;i++){
read(x);
read(y);
read(r);
add(x,y,r);
}
dij(s);
for(int i=1;i<=n;i++){
write(d[i]);
}
return 0;
}UVA247:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1010;
int g[N][N];
map<string,int>H;
string ans[N];
int b[N];
int n,m,cnt,s=0;
string x,y;
signed main(){
while(scanf("%d%d",&n,&m)){
if(n==0&&m==0){
break;
}
memset(b,0,sizeof(b));
memset(g,0,sizeof(g));
H.clear();
cnt=0;
for(int i=1;i<=m;i++){
cin>>x>>y;
if(H[x]==0){
cnt++;
H[x]=cnt;
ans[cnt]=x;
}
if(H[y]==0){
cnt++;
H[y]=cnt;
ans[cnt]=y;
}
g[H[x]][H[y]]=1;
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
g[i][j]|=g[i][k]&&g[k][j];
}
}
}
printf("Calling circles for data set %d:\n",++s);
queue<string> q;
for(int i=1;i<=n;i++){
if(b[i]){
continue;
}
q.push(ans[i]);
for(int j=i+1;j<=n;j++){
if(g[i][j]&&g[j][i]){
q.push(ans[j]),b[j]=1;
}
}
while(q.size()!=1){
cout<<q.front()<<", ";
q.pop();
}
cout<<q.front()<<endl;
q.pop();
}
}
return 0;
}UVA658:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1<<20,M=105;
int n,m,ti[M],b1[M],b2[M],f1[M],f2[M],dis[N];
bool vis[N];
struct node{
int p,v;
bool operator<(const node&k)const{return v>k.v;}
};
void dij(){
priority_queue<node>q;
int s=(1<<n)-1;
q.push({s,0});dis[s]=0;
while(!q.empty()){
int t=q.top().p;q.pop();
if(vis[t])continue;
vis[t]=1;
for(int i=1;i<=m;i++){
int g=t;
if((g&b1[i])!=b1[i])continue;
if((g&b2[i])!=0)continue;
g^=(g&f1[i]);
g|=f2[i];
if(dis[g]<=dis[t]+ti[i])continue;
dis[g]=dis[t]+ti[i];
q.push({g,dis[g]});
}
}
}
int cnt;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
while(cin>>n>>m&&n&&m){
memset(dis,0x3f,sizeof dis);
memset(vis,0,sizeof vis);
for(int i=1;i<=m;i++){
cin>>ti[i];
char c;
b1[i]=b2[i]=f1[i]=f2[i]=0;
for(int j=0;j<n;j++){
cin>>c;
if(c=='+')b1[i]|=(1<<j);
if(c=='-')b2[i]|=(1<<j);
}
for(int j=0;j<n;j++){
cin>>c;
if(c=='+')f2[i]|=(1<<j);
if(c=='-')f1[i]|=(1<<j);
}
}
dij();
cnt++;
cout<<"Product "<<cnt<<'\n';
if(dis[0]==0x3f3f3f3f3f3f3f3f){
cout<<"Bugs cannot be fixed.\n";
}
else{
cout<<"Fastest sequence takes "<<dis[0]<<" seconds.\n";
}
cout<<'\n';
}
return 0;
}UVA10048:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=909;
int n,m,s,d[N][N],vis[N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
for(int Z=1;;Z++){
memset(d,0x3f,sizeof(d));
cin>>n>>m>>s;
if(n==0&&m==0&&s==0)break;
if(Z!=1)cout<<"\n";
cout<<"Case #"<<Z<<"\n";
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
d[x][y]=min(d[x][y],z);
d[y][x]=min(d[y][x],z);
}
for(int i=1;i<=n;i++){
d[i][i]=0;
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
d[i][j]=min(d[i][j],max(d[i][k],d[k][j]));
}
}
}
while(s--){
int x,y;
cin>>x>>y;
if(d[x][y]==0x3f3f3f3f3f3f3f3f){
cout<<"no path\n";
}
else cout<<d[x][y]<<"\n";
}
}
return 0;
}