AcWing University

1.6万

Tkybk_dz

2个月前

// class Solution {
// public:
// string leftRotateString(string str, int n) {
// string s;

// for(int i=n;i<str.size();i)
// s+=str[i];
// for(int i=0;i<n;
i)
// s+=str[i];
// return s;
// }
// };

class Solution {
public:
string leftRotateString(string str, int n) {
reverse(str.begin(), str.end());
reverse(str.begin(), str.end() - n);
reverse(str.end() - n, str.end());
return str;
}
};

3个月前
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
while(n--)
{
int num;
cin>>num;
if(num==1)
{
cout<<"No"<<endl;
continue;
}
bool st=true;
for(int i=2;i*i<=num;++i)
if(num%i==0)
{
st=false;
break;
}
if(st) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}


TLE

#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
while(n--)
{
int num;
cin>>num;
if(num==1)
{
cout<<"No"<<endl;
continue;
}
bool st=true;
for(int i=2;i<=num/i;++i)
if(num%i==0)
{
st=false;
break;
}
if(st) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}


3个月前
#include<iostream>
using namespace std;
bool year(int y)//闰年返回yes,平年返回no
{
if(y%400==0||y%4==0&&y%100!=0)
return true;
else
return false;
}
int main()
{
int y,m,d;
int r[]={0,31,29,31,30,31,30,31,31,30,31,30,31};
int p[]={0,31,28,31,30,31,30,31,31,30,31,30,31};

while(cin>>y>>m>>d)
{
int ans=0;
ans+=d;
if(year(y))//闰年
{
for(int i=m-1;i>=1;--i)
ans+=r[i];
}
else//平年
{
for(int i=m-1;i>=1;--i)
ans+=p[i];
}
cout<<ans<<endl;
}
return 0;
}


AcWing 3218. 日期计算

 #include<iostream>
using namespace std;
bool year(int y)
{
if(y%400==0||y%4==0&&y%100!=0)
return true;//闰年
else
return false;//平年
}
int main()
{
int y,d;
int r[]={0,31,29,31,30,31,30,31,31,30,31,30,31};
int p[]={0,31,28,31,30,31,30,31,31,30,31,30,31};

while(cin>>y>>d)
{
int ans=1;
if(year(y))
{
while(d>r[ans])//从一月份开始,先比较天数和当前月份的大小,天数<当前月份,说明答案就是当前月份
{
d-=r[ans];
ans++;
}
}
else
{
while(d>p[ans])
{
d-=p[ans];
ans++;
}
}
cout<<ans<<endl<<d<<endl;
}

return 0;
}




# include[HTML_REMOVED]

using namespace std;
bool year(int y)//闰年返回yes,平年返回no
{
if(y%400==0||y%4==0&&y%100!=0)
return true;
else
return false;
}
int main()
{
int week[]={7,1,2,3,4,5,6};
int n,m;
cin>>n>>m;
int next=5;//2021-1-1是星期五
for(int i=n;i<=m;++i)
{
cout<<i<<”年:”<<next<<endl;
if(year(i))
{
next=week[(next+366)%7];
}
else
next=week[(next+365)%7];

}
return 0;


}


3个月前

HDU 1213.How Many Tables

#include<iostream>
using namespace std;
int num[100005];
void init(int n)//初始化
{
for(int i=1;i<=n;++i)
num[i]=i;
}

int find(int n)//查找
{
if(n==num[n]) return num[n];
else find(num[n]);
}

void merge(int a,int b)//合并
{
int x=find(a);
int y=find(b);
num[x]=y;
}
int main()
{
int t,n,m;
cin>>t;

while(t--)
{
cin>>n>>m;

ini(n);//初始化

while(m--)
{
int a,b;
cin>>a>>b;

if(find(a)!=find(b))
merge(a,b);//合并
}

int rec=0;
for(int i=1;i<=n;++i)
if(i!=find(i)) rec++;

cout<<n-rec<<endl;//这个地方要注意

}
return 0;
}


#include<iostream>
using namespace std;
const int maxn = 1050;
int s[maxn];
void init()
{
for(int i=1;i<=maxn;++i)//初始化
s[i]=i;
}
int find(int x)//查找
{
return x==s[x]?x:find(s[x]);
}
void merge(int x,int y)//合并
{
x=find(x);
y=find(y);
if(x!=y) s[x]=s[y];
}

int main()
{
int t,n,m,x,y;
cin>>t;
while(t--){
cin>>n>>m;
init();
for(int i=1;i<=m;++i){
cin>>x>>y;
merge(x,y);
}
int ans=0;
for(int i=1;i<=n;++i)//统计有多少个集
if(s[i]==i)
ans++;
cout<<ans<<endl;
}
}


• #### 合并的优化:

int height[maxn];
void init(){
for(int i=1;i<=maxn;++i){
s[i]=i;
height[i]=0;//树的高度
}
}
void merge(int x,int y){//优化合并操作
x=find(x);
y=find(y);
if(height[x]==height[y]){
height[x]=height[x]+1;//合并，树的高度加一
s[y]=x;
}
else{
if(height[x]<height[y]) s[x]=y;
else s[y]=x;
}
}

• #### 查询的优化—路径压缩:

int find(int x){
if(x!=s[x]) s[x]=find(s[x]);//路径压缩
return s[x];
}
//这样其实还需要递归，但是只递归一次就好了，例如没有路径压缩时，要想求1的根结点，首先要到2-3-4，路径压缩之后，就是1-4.


int find(int x){
int r=x;
while(s[r]!=r) r=s[r];//找到根结点
int i=x,j;
while(i!=r){
j=s[i];//用临时变量j记录
s[i]=r;//把路径上元素的集改为根结点
i=j;
}
return r;
}


#include<iostream>
using namespace std;
const int maxn = 1050;
int s[maxn];
int height[maxn];
void init(){
for(int i=1;i<=maxn;++i){
s[i]=i;
height[i]=0;//树的高度
}
}
int find(int x){
if(x!=s[x]) s[x]=find(s[x]);//路径压缩
return s[x];
}
void merge(int x,int y){//优化合并操作
x=find(x);
y=find(y);
if(height[x]=height[y]){
height[x]=height[x]+1;//合并，树的高度加一
s[y]=x;
}
else{
if(height[x]<height[y]) s[x]=y;
else s[y]=x;
}
}

int main()
{
int t,n,m,x,y;
cin>>t;
while(t--){
cin>>n>>m;
init();
for(int i=1;i<=m;++i){
cin>>x>>y;
merge(x,y);
}
int ans=0;
for(int i=1;i<=n;++i)//统计有多少个集
if(s[i]==i)
ans++;
cout<<ans<<endl;
}
}


#include<iostream>
using namespace std;
const int maxn=50005;
int s[maxn];
void init(int n)
{
for(int i=1;i<=n;++i)
s[i]=i;
}
int find(int x)
{

if(x==s[x]) return s[x];
else find(s[x]);
}
void merge(int x,int y)
{
x=find(s[x]);
y=find(s[y]);
s[y]=x;
}
int main()
{
int rec=1;
int n,m;
while(cin>>n>>m)
{
if(n==0&&m==0) break;

init(n);

int a,b,ans=0;
while(m--)
{
cin>>a>>b;
if(find(a)!=find(b))
merge(a,b);
}

for(int i=1;i<=n;++i)
if(i==s[i]) ans++;

cout<<"Case "<<rec<<": "<<ans<<endl;
rec++;
}
return 0;
}


#include<iostream>
using namespace std;
const int maxn=50005;
int s[maxn];
void init(int n)
{
for(int i=1;i<=n;++i)
s[i]=i;
}
int find(int x)
{
if(s[x]!=x) s[x]=find(s[x]);
else return s[x];
//  if(x==s[x]) return s[x];
//  else find(s[x]);
}
void merge(int x,int y)
{
x=find(s[x]);
y=find(s[y]);
s[y]=x;
}
int main()
{
int rec=1;
int n,m;
while(cin>>n>>m)
{
if(n==0&&m==0) break;

init(n);

int a,b,ans=0;
while(m--)
{
cin>>a>>b;
if(find(a)!=find(b))
merge(a,b);
}

for(int i=1;i<=n;++i)
if(i==s[i]) ans++;

cout<<"Case "<<rec<<": "<<ans<<endl;
rec++;
}
return 0;
}


#include<iostream>
using namespace std;
int num[100005];
void init(int n)//初始化
{
for(int i=1;i<=n;++i)
num[i]=i;
}

int find(int n)//查找
{
if(n==num[n]) return num[n];
else find(num[n]);
}

void merge(int a,int b)
{
int x=find(a);
int y=find(b);
num[x]=y;
}
int main()
{
int n,m;
cin>>n>>m;

init(n);//初始化

while(m--)
{
char c;
int a,b;
cin>>c>>a>>b;
if(c=='M')
{
if(find(a)!=find(b))
merge(a,b);
}
else
{
if(find(a)==find(b)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}

return 0;
}


#include<iostream>
using namespace std;
int num[100005];
void init(int n)//初始化
{
for(int i=1;i<=n;++i)
num[i]=i;
}

int find(int n)//查找
{
if(n!=num[n])  num[n]=find(num[n]);
else return num[n];
}

void merge(int a,int b)
{
int x=find(a);
int y=find(b);
num[x]=y;
}
int main()
{
int n,m;
cin>>n>>m;

init(n);//初始化

while(m--)
{
char c;
int a,b;
cin>>c>>a>>b;
if(c=='M')
{
if(find(a)!=find(b))
merge(a,b);
}
else
{
if(find(a)==find(b)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}

return 0;
}


#include<iostream>
using namespace std;
const int maxn=30005;
int s[maxn];
void init(int n)
{
for(int i=0;i<maxn;++i)
s[i]=i;
}
int find(int x)
{
if(x!=s[x]) s[x]=find(s[x]);
else return s[x];
}
void merge(int x,int y)
{
x=find(x);
y=find(y);
s[y]=x;
}
int main()
{
int n,m,k;
int num[maxn];
while(cin>>n>>m)
{
if(n==0&&m==0) break;
init(n);
while(m--)//挨个读入每个小组
{
cin>>k;
int num[maxn];
for(int i=1;i<=k;++i)
cin>>num[i];//将每一个小组成员的编号读入数组num中
int first=find(num[1]);//用变量first记录小组第一个人的根结点
for(int i=2;i<=k;++i)//将小组内成员进行合并
if(first!=find(num[i]))
merge(first,num[i]);
}
int zero=find(0);//找到0号成员的根结点
int ans=1;//记录可疑对象的数量
for(int i=1;i<n;++i)//遍历整个数组，寻找可疑对象
if(find(i)==zero) ans++;

cout<<ans<<endl;
}
return 0;
}


#include<iostream>
using namespace std;
const int maxn=30005;
int s[maxn];
void init(int n)
{
for(int i=0;i<maxn;++i)
s[i]=i;
}
int find(int x)
{
if(x!=s[x]) s[x]=find(s[x]);
return s[x];
}
void merge(int x,int y)
{
x=find(x);
y=find(y);
s[y]=x;
}
int main()
{
int n,m,k;
int num[maxn];
while(cin>>n>>m)
{
if(n==0&&m==0) break;
init(n);
while(m--)//挨个读入每个小组
{
cin>>k;
int num[maxn];
for(int i=1;i<=k;++i)
cin>>num[i];//将每一个小组成员的编号读入数组num中
int first=find(num[1]);//用变量first记录小组第一个人的根结点
for(int i=2;i<=k;++i)//将小组内成员进行合并
if(first!=find(num[i]))
merge(first,num[i]);
}
int zero=find(0);//找到0号成员的根结点
int ans=1;//记录可疑对象的数量
for(int i=1;i<n;++i)//遍历整个数组，寻找可疑对象
if(find(i)==zero) ans++;

cout<<ans<<endl;
}
return 0;
}


#include<iostream>
using namespace std;
const int maxn=100005;
int s[maxn],sum[maxn];
void init(int n)
{
for(int i=1;i<=n;++i)
s[i]=i;
}
int find(int x)
{
if(x!=s[x]) s[x]=find(s[x]);
return s[x];
}
void merge(int x,int y)
{
x=find(x);
y=find(y);
s[y]=x;
}

int main()
{
int n,m;
cin>>n>>m;
init(n);

while(m--)
{
string s;
int a,b;
cin>>s;
if(s=="C")
{
cin>>a>>b;
if(find(a)!=find(b))
merge(a,b);
}
else if(s=="Q1")
{
cin>>a>>b;
if(find(a)==find(b)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
else
{
cin>>a;
int ans=0;
for(int i=1;i<=n;++i)
if(find(a)==find(i)) ans++;

cout<<ans<<endl;
}
}
return 0;
}


TLE了,对合并进行优化:

#include<iostream>
using namespace std;
const int maxn=100005;
int s[maxn],sum[maxn],height[maxn];
void init(int n)
{
for(int i=1;i<=n;++i)
{
s[i]=i;
height[i]=0;
}

}
int find(int x)
{
if(x!=s[x]) s[x]=find(s[x]);
return s[x];
}
void merge(int x,int y)
{
x=find(x);
y=find(y);
if(height[x]==height[y])
{
s[y]=x;
height[x]++;
}
else
{
if(height[x]<height[y]) s[x]=y;
else s[y]=x;
}
}

int main()
{
int n,m;
cin>>n>>m;
init(n);

while(m--)
{
string s;
int a,b;
cin>>s;
if(s=="C")
{
cin>>a>>b;
if(find(a)!=find(b))
merge(a,b);
}
else if(s=="Q1")
{
cin>>a>>b;
if(find(a)==find(b)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
else
{
cin>>a;
int ans=0;
for(int i=1;i<=n;++i)
if(find(a)==find(i)) ans++;

cout<<ans<<endl;
}
}
return 0;
}


#include<iostream>
using namespace std;
const int maxn=100005;
int s[maxn],sum[maxn],height[maxn];
void init(int n)
{
for(int i=1;i<=n;++i)
{
s[i]=i;
height[i]=0;
sum[i]=1;
}

}
int find(int x)
{
if(x!=s[x]) s[x]=find(s[x]);
return s[x];
}
void merge(int x,int y)
{
x=find(x);
y=find(y);
sum[x]=sum[x]+sum[y];
sum[y]=0;
s[y]=x;
}

int main()
{
int n,m;
cin>>n>>m;
init(n);

while(m--)
{
string s;
int a,b;
cin>>s;
if(s=="C")
{
cin>>a>>b;
if(find(a)!=find(b))
merge(a,b);
}
else if(s=="Q1")
{
cin>>a>>b;
if(find(a)==find(b)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
else
{
cin>>a;
cout<<sum[find(a)]<<endl;
}
}
return 0;
}


AC了,再加上合并优化后看看快多少:

#include<iostream>
using namespace std;
const int maxn=100005;
int s[maxn],sum[maxn],height[maxn];
void init(int n)
{
for(int i=1;i<=n;++i)
{
s[i]=i;
height[i]=0;
sum[i]=1;
}

}
int find(int x)
{
if(x!=s[x]) s[x]=find(s[x]);
return s[x];
}
void merge(int x,int y)
{
x=find(x);
y=find(y);
if(height[x]==height[y])
{
s[y]=x;
height[x]++;
sum[x]+=sum[y];
sum[y]=0;
}
else
{
if(height[x]<height[y])
{
s[x]=y;
sum[y]+=sum[x];
sum[x]=0;
}
else
{
s[y]=x;
sum[x]+=sum[y];
sum[y]=0;
}
}
}

int main()
{
int n,m;
cin>>n>>m;
init(n);

while(m--)
{
string s;
int a,b;
cin>>s;
if(s=="C")
{
cin>>a>>b;
if(find(a)!=find(b))
merge(a,b);
}
else if(s=="Q1")
{
cin>>a>>b;
if(find(a)==find(b)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
else
{
cin>>a;
cout<<sum[find(a)]<<endl;
}
}
return 0;
}


AcWing 2069. 网络分析

#include<iostream>
using namespace std;
const int maxn=10005;
int s[maxn];
long long sum[maxn];
bool initi(int n)
{
for(int i=1;i<=n;++i)
s[i]=i;
}
int find(int x)
{
if(x!=s[x]) s[x]=find(s[x]);
return s[x];
}
void merge(int x,int y)
{
x=find(s[x]);
y=find(s[y]);
s[y]=x;
}
int main()
{
int n,m;
cin>>n>>m;
initi(n);

int c,a,b;
while(m--)
{
cin>>c>>a>>b;
if(c==1)//连接
merge(a,b);
else//发送消息
for(int i=1;i<=n;++i)
if(find(i)==find(a)) sum[i]+=b;
}
for(int i=1;i<=n;++i)
cout<<sum[i]<<" ";
return 0;
}





4个月前

A + B: A和B的位数小于等于$10^6$;
A - B: A和B的位数小于等于$10^6$;
A x a: A的位数小于等于$10^6$,a的值小于等于$10^9$.

#include<iostream>
#include<vector>
using namespace std;
int main()
{
string s1,s2;
vector<int> a,b,c;

cin>>s1>>s2;

for(int i=s1.size()-1;i>=0;--i) a.push_back(s1[i]-'0');
for(int i=s2.size()-1;i>=0;--i) b.push_back(s2[i]-'0');
//当把string中的数字转换成整数时就是这样:-'0'!!!

int d=0;//d表示进位
for(int i=0;i<a.size()&&i<b.size();++i)
{
c.push_back((a[i]+b[i]+d)%10);
d=(a[i]+b[i]+d)/10;
}

if(a.size()>c.size())
{
for(int i=c.size();i<a.size();++i)
{
c.push_back((a[i]+d)%10);
d=(a[i]+d)/10;
}
}

if(b.size()>c.size())
{
for(int i=c.size();i<b.size();++i)
{
c.push_back((b[i]+d)%10);
d=(b[i]+d)/10;
}
}

if(d) c.push_back(d);//最后还有进位时

for(int i=c.size()-1;i>=0;--i)//倒序输出
cout<<c[i];

return 0;
}


y总的:

#include<iostream>
#include<vector>
using namespace std;

{
if (A.size() < B.size()) return add(B, A);//这个地方牛逼！！！

vector<int> C;
int t = 0;
for (int i = 0; i < A.size(); i ++ )
{
t += A[i];
if (i < B.size()) t += B[i];//这个地方也牛逼！！！
C.push_back(t % 10);
t /= 10;
}

if (t) C.push_back(1);
return C;
}

int main()
{
string a,b;
vector<int> A,B;
cin>>a>>b;
for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');

for(int i=C.size()-1;i>=0;i--) cout<<C[i];

return 0;
}


• 高精度减法：

AcWing 792. 高精度减法

两个字符串比较大小，当第一次出现在相同位置两个字符不相等时，两个字符中ASCII大的所在字符串就大

#include<iostream>
#include<vector>
using namespace std;
{
vector<int> c;

int d=0;
for(int i=0;i<a.size();++i)
{
if(i<b.size())
{
if(a[i]-b[i]-d<0)
{
c.push_back(10+a[i]-b[i]-d);
d=1;
}
else
{
c.push_back(a[i]-b[i]-d);
d=0;
}
}
else
{
if(a[i]-d<0)
{
c.push_back(10+a[i]-d);
d=1;
}
else
{
c.push_back(a[i]-d);
d=0;
}
}
}
return c;

}
int main()
{
bool st;
string s1,s2;
cin>>s1>>s2;

vector<int>a,b;

if(s1.size()<s2.size()||(s1.size()==s2.size()&&s1<s2))
{
swap(s1,s2);
st=true;
}//这一块很有必要,可以写几个样例试试看:8888 99999;8888 9999等

for(int i=s1.size()-1;i>=0;--i) a.push_back(s1[i]-'0');
for(int i=s2.size()-1;i>=0;--i) b.push_back(s2[i]-'0');

while(true)
{
if(c.size()==1) break;

if(c[c.size()-1]==0) c.pop_back();
else break;
}

if(st) cout<<"-";

for(int i=c.size()-1;i>=0;--i)
cout<<c[i];

return 0;
}


y总代码:

#include<iostream>
#include<vector>
using namespace std;

//判断是否有A>=B
bool cmp(vector<int> &A, vector<int> &B)
{
if(A.size()!=B.size()) return A.size()>B.size();
for(int i=A.size()-1;i>=0;--i)
if(A[i]!=B[i])
return A[i]>B[i];
return true;
}

//C=A-B
vector<int> sub(vector<int> &A,vector<int> &B)
{
vector<int> C;
for(int i=0,t=0;i<A.size();++i)
{
t=A[i]-t;
if(i<B.size()) t-=B[i];
C.push_back((t+10)%10);
if(t<0) t=1;
else t=0;
}
while(C.size()>1&&C.back()==0) C.pop_back();

return C;
}
int main()
{
string a,b;
vector<int> A,B;

cin>>a>>b;
for(int i=a.size()-1;i>=0;--i) A.push_back(a[i]-'0');
for(int i=b.size()-1;i>=0;--i) B.push_back(b[i]-'0');

if(cmp(A,B))
{
vector<int> C=sub(A,B);
for(int i=C.size()-1;i>=0;--i) cout<<C[i];
}
else
{
vector<int> C=sub(B,A);
cout<<"-";
for(int i=C.size()-1;i>=0;--i) cout<<C[i];
}
return 0;
}



• 高精度乘法:
高精度乘法还是模拟我们列竖式的过程:
#include<iostream>
#include<vector>
using namespace std;

vector<int> mul(vector<int> &a,vector<int> &b)
{
vector<int> d[5];
vector<int> c;
for(int i=0;i<b.size();++i)
{
for(int k=0;k<i;++k)
d[i].push_back(0);//将尾部进行加零处理

int t=0;
for(int j=0;j<a.size();++j)
{
d[i].push_back((b[i]*a[j]+t)%10);
t=(b[i]*a[j]+t)/10;
}
if(t) d[i].push_back(t);
}//将b的每一位与a的每一位相乘

for(int i=0;i<b.size()-1;++i)
{
for(int j=d[i].size();j<d[b.size()-1].size();++j)
d[i].push_back(0);
}//将每行尾部进行加零

int t=0;
for(int i=0;i<d[b.size()-1].size();++i)
{
int sum=0;
for(int j=0;j<b.size();++j)
{
sum+=d[j][i];
}
c.push_back((sum+t)%10);
t=(sum+t)/10;
}//执行的是相加处理

if(t) c.push_back(t);

return c;
}
int main()
{
string s1,s2;
vector<int> a,b,c;
cin>>s1>>s2;

if(s1=="0"||s2=="0")
{
cout<<0;
return 0;
}

for(int i=s1.size()-1;i>=0;--i) a.push_back(s1[i]-'0');
for(int i=s2.size()-1;i>=0;--i) b.push_back(s2[i]-'0');

if(a.size()<b.size()) c=mul(b,a);
else c=mul(a,b);//习惯上len(a)>len(b)

for(int i=c.size()-1;i>=0;--i)
cout<<c[i];

return 0;
}



y总

#include<iostream>
#include<vector>
using namespace std;
vector<int> mul(vector<int> &a,int num)
{
vector<int> c;

int t=0;
for(int i=0;i<a.size();++i)
{
c.push_back((a[i]*num+t)%10);
t=(a[i]*num+t)/10;
}
if(t) c.push_back(t);

return c;
}
int main()
{
string s;
int num;
cin>>s>>num;
vector<int> a;
if(num==0)
{
cout<<0;
return 0;
}
for(int i=s.size()-1;i>=0;--i) a.push_back(s[i]-'0');

vector<int> b;
b=mul(a,num);

for(int i=b.size()-1;i>=0;--i) cout<<b[i];
return 0;
}


#include<iostream>
#include<vector>
using namespace std;
{
vector<int> c;
if(a.size()<b.size())
swap(a,b);

int t=0;
for(int i=0;i<a.size();++i)
{
t+=a[i];
if(i<b.size()) t+=b[i];
c.push_back(t%10);
t/=10;
}
if(t) c.push_back(1);
return c;
}
int main()
{
int n;
string s;
vector<int>a,b;
cin>>n;
getchar();
while(n--)
{
a.clear();b.clear();//每组都要清空

while(cin>>s&&s!="0")
{
if(s=="") continue;

if(a.empty())
for(int i=s.size()-1;i>=0;--i) a.push_back(s[i]-'0');

else
{
for(int i=s.size()-1;i>=0;--i) b.push_back(s[i]-'0');
}

b.clear();//输入一组后必须要清空
}

for(int i=a.size()-1;i>=0;--i)
cout<<a[i];

cout<<endl;

if(n) cout<<endl;
}

return 0;
}


#include<iostream>
#include<vector>
using namespace std;
{
vector<int> c;
if(a.size()<b.size())
swap(a,b);

int t=0;
for(int i=0;i<a.size();++i)
{
t+=a[i];
if(i<b.size()) t+=b[i];
c.push_back(t%10);
t/=10;
}
if(t) c.push_back(1);
return c;
}
int main()
{
int n;
string s;
vector<int>a,b;
cin>>n;
getchar();
while(n--)
{
a.clear();b.clear();//每组都要清空

int num=0;
while(cin>>s&&s!="0")
{
num++;

if(s=="") continue;

if(a.empty())
for(int i=s.size()-1;i>=0;--i) a.push_back(s[i]-'0');

else
{
for(int i=s.size()-1;i>=0;--i) b.push_back(s[i]-'0');
}

b.clear();//输入一组后必须要清空
}

if(s=="0"&&num==0) cout<<"0";
else
{
for(int i=a.size()-1;i>=0;--i)
cout<<a[i];
}

cout<<endl;

if(n) cout<<endl;
}

return 0;
}


1. HDU.1042 N!
百度可知10000!是有 35660 位数



4个月前

POJ 1602.Text Reverse
//直接暴力:

#include<iostream>
using namespace std;
#include<cmath>
int main()
{
int n;
cin>>n;
getchar();

while(n--)
{
string s;

getline(cin,s);
for(int first=0,last=0;last<s.size();++last)
{
while(s[last]!=' '&&last<s.size())
last++;

for(int i=first,j=last-1;i<j;++i,j--)
swap(s[i],s[j]);

first=last+1;
}

cout<<s<<endl;
}
return 0;
}


//使用stack:

#include<iostream>
#include<stack>
using namespace std;
int main()
{
int n;
char ch;
cin>>n;
getchar();
while(n--)
{
stack<char> s;
while(true)
{
ch=getchar(); //一次读入一个字符
if(ch==' '||ch=='\n'||ch==EOF)
{
while(!s.empty())
{
cout<<s.top(); //输出栈顶
s.pop(); //清除栈顶
}
if(ch=='\n'||ch==EOF) break;
cout<<" ";
}
else s.push(ch); // 入栈
}
cout<<endl;
}
return 0;
}


#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
getchar(); //当先输入一个证书，然后再输入字符串的时候，在输入整数后要用getchar()吸收掉后边的回车
while(n--)
{
string s;
getline(cin,s);

for(int i=0,j=0;j<s.size();++i,++j)
{
while(s[j+1]==s[i]&&j<s.size())
j++;

if(i==j) cout<<s[i];
else cout<<j-i+1<<s[i];

i=j;
}
cout<<endl;
}
return 0;
}


4个月前

## 动态数组:

### 习题:

POJ 4841.圆桌问题

#include<iostream>
using namespace std;
int main()
{
string s;
int n,m;
while(cin>>n>>m)
{
for(int i=1;i<=2*n;++i)
s[i]='G'; //先将数组初始化全为好人

int run=1;//相当于一个指针，一直在围着桌子转
for(int i=1;i<=n;++i)
{
int sum=0;
while(1)
{
if(s[run%(2*n+1)]=='G') sum++;//赶走以后位置还在那,sum计数时要跳过已经赶走的
if(sum==m) break;//当又跳过m个人以后,这时需要跳出来赶人了
run++;
}
s[run%(2*n+1)]='B';
}
for(int i=1;i<=2*n;++i)
{
cout<<s[i];
if(i%50==0) cout<<endl;
}

cout<<endl<<endl;
}
return 0;
}


#include<iostream>
using namespace std;
#include<vector>
int main()
{
vector<int> table; //模拟圆桌
int n, m;
while (cin >> n >> m)
{
for (int i = 0; i < 2 * n; ++i)
table.push_back(i); //初始化

int pos = 0; //记录当前位置
for (int i = 1; i <= n; ++i) //赶走n个人
{
pos = (pos + m - 1) % table.size(); //圆桌是个环，取余处理
table.erase(table.begin() + pos); //赶走坏人，table人数减1
}
int j = 0;
for (int i = 0; i < 2 * n; ++i) //打印预先安排座位
{
if (!(i % 50) && i) cout << endl; //50个字母一行
if (j < table.size() && i == table[j]) //table留下的都是好人
{
j++;
cout << "G";
}
else
cout << "B";
}
cout << endl << endl; //留一个空行
}
return 0;
}


#include<iostream>
#include<list>
using namespace std;
int main()
{
list<int>table;
int n,m;
while(cin>>n>>m)
{
table.clear(); // 清空list容器
for(int i=0;i<2*n;++i) //将所有人的编号放入list
table.push_back(i);
list<int>::iterator it=table.begin();
while(table.size()>n){ //只要还有不止n个人，就要找一个坏人让其出列
for(int i=1;i<m;++i){ //报数
++it;
if(it==table.end())
it=table.begin();
}
it=table.erase(it); //删除元素后，迭代器失效，要重新让迭代器指向被删元素的后面

if(it==table.end())
it=table.begin();
}

it=table.begin();

for(int i=0;i<2*n;++i)
{
if(!(i%50)&&i) cout<<endl;
if(it!=table.end()&&i==*it){
it++;
cout<<"G";
}
else
cout<<"B";
}
cout<<endl<<endl;
}
return 0;
}


AcWing 82. 圆圈中最后剩下的数字

class Solution {
public:
int lastRemaining(int n, int m){
bool st[100000];
for(int i=0;i<n;++i) st[i]=false;

int run=0;
for(int i=1;i<n;++i)//n个数，要求最后留下的1个数，所以要循环删除n-1次
{
int sum=0;
while(1)
{
if(st[run%n]==false) sum++;
if(sum==m) break;
run++;
}
st[run%n]=true;//表示被删除
}
for(int i=0;i<n;++i)
if(st[i]==false)
return i; //将剩下的最后一个元素返回
}
};



class Solution {
public:
int lastRemaining(int n, int m){
vector<int> a;

for(int i=0;i<n;++i) a.push_back(i);

int pos=0;

for(int i=1;i<n;++i)
{
pos=(pos+m-1)%a.size();
a.erase(a.begin()+pos);
}

return *a.begin();

}
};


直接暴力用时195ms,vector用时26ms

class Solution {
public:
int lastRemaining(int n, int m){
if(n==1) return 0;
return (lastRemaining(n -1,m)+m)%n;
}
};


这个用时22ms.

AcWing 1455.招聘

#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> table;

int t;
cin>>t;

while(t--)
{
table.clear();
int n,m,a[1010];
cin>>n>>m;

for(int i=0;i<m;++i)
cin>>a[i];

for(int i=0;i<n;++i) table.push_back(i); //初始化

int pos=0;

for(int i=1;i<=n;++i)
{
pos=(pos+a[(i-1)%m]-1)%table.size();

table.erase(table.begin()+pos);
}

cout<<*table.begin()<<endl;
}
return 0;
}


#include<iostream>
#include<list>
using namespace std;
int main()
{
list<int> table;
int t;
cin>>t;
while(t--)
{
table.clear(); // 清空list容器
int n,m,a[1010];
cin>>n>>m;
for(int i=0;i<m;++i)
cin>>a[i];

for(int i=0;i<n;++i) table.push_back(i); //将编号放入list

list<int>::iterator it=table.begin();

for(int j=1;j<n;++j){ //只要还有不止一个人，就要找一个人将其淘汰
for(int i=1;i<a[(j-1)%m];++i){ //报数
++it;
if(it==table.end())
it=table.begin();
}
it=table.erase(it); //删除元素后，迭代器失效，要重新让迭代器指向被删元素的后面

if(it==table.end())
it=table.begin();
}
cout<<table.front()<<endl; //front返回第一个元素的引用
}
return 0;
}


## 栈:

### 习题:

POJ 1602.Text Reverse
//直接暴力:

#include<iostream>
using namespace std;
#include<cmath>
int main()
{
int n;
cin>>n;
getchar();

while(n--)
{
string s;

getline(cin,s);
for(int first=0,last=0;last<s.size();++last)
{
while(s[last]!=' '&&last<s.size())
last++;

for(int i=first,j=last-1;i<j;++i,j--)
swap(s[i],s[j]);

first=last+1;
}

cout<<s<<endl;
}
return 0;
}


//使用stack:

#include<iostream>
#include<stack>
using namespace std;
int main()
{
int n;
char ch;
cin>>n;
getchar();
while(n--)
{
stack<char> s;
while(true)
{
ch=getchar(); //一次读入一个字符
if(ch==' '||ch=='\n'||ch==EOF)
{
while(!s.empty())
{
cout<<s.top(); //输出栈顶
s.pop(); //清除栈顶
}
if(ch=='\n'||ch==EOF) break;
cout<<" ";
}
else s.push(ch); // 入栈
}
cout<<endl;
}
return 0;
}


## 队列:

### 习题

#include<iostream>
#include<queue>
#include<stack>
using namespace std;
queue<int> q;
stack<int> st;
void fifo()
{
if (q.empty()) cout << "None" << endl;
else
{
cout << q.front() << endl;
q.pop();
}

}
void filo()
{
if (st.empty()) cout << "Nosane" << endl;
else
{
cout << st.top() << endl;
st.pop();
}
}
int main()
{
int n, m;
cin >> m;
while (m--)
{
string s, io;
int num;
cin >> n >> s;

if (s == "FIFO")
{
q = queue<int>();
while (n--)
{
cin >> io;
if (io == "IN")
{
cin >> num;
q.push(num);
}
else fifo();
}
}
else
{
st = stack<int>();
while (n--)
{
cin >> io;
if (io == "IN")
{
cin >> num;
st.push(num);
}
else filo();
}
}
}
return 0;
}


#include<bits/stdc++.h>
using namespace std;
int main()
{
int t,n,temp;
cin>>t;
while(t--){
string str,str1;
queue<int>Q;
stack<int>S;
cin>>n>>str;
for(int i=0;i<n;++i){
if(str=="FIFO"){ //队列
cin>>str1;
if(str1=="IN"){
cin>>temp; Q.push(temp);
}
if(str1=="OUT"){
if(Q.empty()) cout<<"None"<<endl;
else{
cout<<Q.front()<<endl;
Q.pop();
}

}
}
else{ //栈
cin>>str1;
if(str1=="IN"){
cin>>temp; S.push(temp);
}
if(str1=="OUT"){
if(S.empty()) cout<<"None"<<endl;
else{
cout<<S.top()<<endl;
S.pop();
}
}
}
}
}
return 0;
}


4个月前
• 一、图的深度优先遍历
• 二、图的广度优先遍历
• 三、城市地——图的深度优先遍历(练习)
• 四、最少转机——图的广度优先遍历(练习)
• 五、最短路径
• 只有五行的算法———Floyd-Warshall
• Dijkstra算法————通过边实现松弛
• Bellman-Ford————解决负权边
• Bellman-Ford的队列优化
• 最短路径算法对比分析

## 一、图的深度优先遍历

### 问题引入:

void dfs(int cur) //cur是当前所在的顶点编号
{
cout << cur << " ";
sum++; //每访问一个顶点sum就加1
if (sum == n) return; //所有的顶点都已经访问过则直接退出
for (i = 1; i <= n; ++i) //从1号顶点到n号顶点依次尝试，看哪些顶点与当前顶点cur有边相连
{
//判断当前节点cur到顶点i是否有边，并判断顶点i是否访问过
if (e[cur][i] = 1 && book[i] == 0)
{
book[i] = 1; //标记顶点i已经访问过
dfs(i); //从顶点i再出发继续遍历
}
}
return;
}


cur—存储的是当前正在遍历的顶点；

#include<iostream>
using namespace std;
int book[101], sum, n, e[101][101];
void dfs(int cur) //cur是当前所在的顶点编号
{
cout << cur << " ";
sum++; //每访问一个顶点sum就加1
if (sum == n) return; //所有的顶点都已经访问过则直接退出
for (int i = 1; i <= n; ++i) //从1号顶点到n号顶点依次尝试，看哪些顶点与当前顶点cur有边相连
{
//判断当前节点cur到顶点i是否有边，并判断顶点i是否访问过
if (e[cur][i] == 1 && book[i] == 0)
{
book[i] = 1; //标记顶点i已经访问过
dfs(i); //从顶点i再出发继续遍历
}
}
return；
}
int main()
{
int m, a, b;
cin >> n >> m;
//初始化二维矩阵
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (i == j) e[i][j] = 0;
else e[i][j] = 99999999; //我们在这里假设999999999为正无穷

//读入顶点之间的边
for (int i = 1; i <= m; ++i)
{
cin >> a >> b;
e[a][b] = 1;
e[b][a] = 1; //这里是无向图，所以需要将e[b][a]也赋为1
}

//从1号城市出发
book[1] = 1; //标记1号顶点已访问
dfs(1); //从1号顶点开始遍历

return 0;
}


## 二、图的广度优先遍历

### 问题引入:

#include<iostream>
using namespace std;
int book[101], sum, n, e[101][101];

int main()
{
int n, m, a, b, cur, book[101] = { 0 }, e[101][101];
cin >> n >> m;
//初始化二维矩阵
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (i == j) e[i][j] = 0;
else e[i][j] = 99999999; //我们在这里假设999999999为正无穷

//读入顶点之间的边
for (int i = 1; i <= m; ++i)
{
cin >> a >> b;
e[a][b] = 1;
e[b][a] = 1; //这里是无向图，所以需要将e[b][a]也赋为1
}

//队列初始化
tail = 1;

//从1号顶点出发，将1号顶点加入队列
que[tail] = 1;
tail++;
book[1] = 1; //标记1号顶点已访问

//当队列不为空的时候循环
{
for (int i = 1; i <= n; ++i) //从1~n依次尝试
{
//判断从顶点cur到顶点i是否有边，并判断顶点i是否已经访问过
if (e[cur][i] == 1 && book[i] == 0)
{
//如果从顶点cur到顶点i有边，并且顶点i没有被访问过，则将顶点i入队
que[tail] = i;
tail++;
book[i] = 1; //标记顶点i已访问
}
//如果tail大于n，则表明所有顶点都已经被访问过
if (tail > n)
break;
}

}

for (int i = 1; i < tail; ++i)
cout << que[i]<<" ";

return 0;
}


使用深度优先搜索和广度优先搜索来遍历图都将会得到这个图的生成树。那么什么叫做生成树，生成树又有哪些作用呢？
这个后边再讨论，下面我们先来看看图有什么作用，它究竞能解决什么实际问题。

## 三、城市地——图的深度优先遍历(练习)

### 代码如下:

#### 自己根据上边思路改的:

#include<iostream>
using namespace std;
int book[101], sum, n, e[101][101];
int dmin = 999999999;//表示最短长度
int num = 0; //当前走了多少米了
void dfs(int cur) //cur是当前所在的顶点编号
{

sum++; //每访问一个顶点sum就加1

if (cur == 5)
if (num < dmin)
{
dmin = num;
return;
}

if (sum == n) return; //所有的顶点都已经访问过则直接退出
for (int i = 1; i <= n; ++i) //从1号顶点到n号顶点依次尝试，看哪些顶点与当前顶点cur有边相连
{
//判断当前节点cur到顶点i是否有边，并判断顶点i是否访问过
if (e[cur][i] > 0 && e[cur][i] < 999999999 && book[i] == 0)
{
book[i] = 1; //标记顶点i已经访问过
num += e[cur][i];
dfs(i); //从顶点i再出发继续遍历
num -= e[cur][i];
book[i] = 0; //上边这两行一定不能少
}
}
return;
}
int main()
{
int m, a, b;
cin >> n >> m;
//初始化二维矩阵
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (i == j) e[i][j] = 0;
else e[i][j] = 99999999; //我们在这里假设999999999为正无穷

//读入顶点之间的边
for (int i = 1; i <= m; ++i)
{
int dis;
cin >> a >> b >> dis;
e[a][b] = dis;

}

//从1号城市出发
book[1] = 1; //标记1号顶点已访问
dfs(1); //从1号顶点开始遍历

cout << dmin;

return 0;
}


#### 答案给出的代码:

#include<iostream>
using namespace std;
int dmin = 999999999, book[101], n, e[101][101];

//cure是当前所在城市的编号，dis是当前已经走过的路程
void dfs(int cur, int dis)
{
//如果当前走过的路程已经大于当之前找到的最短路，则没有必要再往下尝试了，立即返回
if (dis > dmin) return;
if (cur == n) //判断是否到达了目标城市
{
if (dis < dmin) dmin = dis; //更新最小值
return;
}

for (int j = 1; j <= n; ++j) //从1号城市到n号城市依次尝试
{
////判断当前城市cur到城市j是否有路，并判断城市j是否在已走过的路径中
if (e[cur][j] != 99999999 && book[j] == 0)
{
book[j] = 1; //标记城市j已经在路径中
dfs(j, dis + e[cur][j]); //从城市j再出发，继续寻找目标城市
book[j] = 0; //之前一步探索完毕后，取消对城市j的标记
}
}
return;
}
int main()
{
int m, a, b, c;
cin >> n >> m;
//初始化二维矩阵
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (i == j) e[i][j] = 0;
else e[i][j] = 99999999; //我们在这里假设999999999为正无穷

//读入顶点之间的边
for (int i = 1; i <= m; ++i)
{
cin >> a >> b >> c;
e[a][b] = c;

}

//从1号城市出发
book[1] = 1; //标记1号顶点已访问
dfs(1, 0); //从1号顶点开始遍历

cout << dmin;

return 0;
}


### 注意:

我们使用了二维数组来存储这个图（顶点和边的关系)，这种存储方法叫做图的邻接矩阵表示法。
本节的解法中存储图的方法还有很多种，比如邻接表等，我们后面再做详细讲解。
此外求图上两点之间的最短路径，除了使用深度优先搜索以外，还可以使用广度优先搜索、Floyd、Bellman-Ford、Dijkstra等

## 四、最少转机——图的广度优先遍历(练习)

### 代码如下:

#### 自己思路代码:

#include<iostream>
using namespace std;
int book[101], sum, n, e[101][101];

int main()
{
int n, m, a, x, y, b, cur, book[101] = { 0 }, e[101][101];
cin >> n >> m >> x >> y;
//初始化二维矩阵
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (i == j) e[i][j] = 0;
else e[i][j] = 99999999; //我们在这里假设999999999为正无穷

//读入顶点之间的边
for (int i = 1; i <= m; ++i)
{
cin >> a >> b;
e[a][b] = 1;
e[b][a] = 1; //这里是无向图，所以需要将e[b][a]也赋为1
}

//队列初始化
tail = 1;

//从x号顶点出发，将x号顶点加入队列
que[tail] = x;
tail++;
book[x] = 1; //标记x号顶点已访问

int min=0;//表示最少转机次数
//当队列不为空的时候循环
{

if(book[y]==1) break;//当y城市进入队列时，这时结束就行了

min++;

for (int i = 1; i <= n; ++i) //从1~n依次尝试
{
//判断从顶点cur到顶点i是否有边，并判断顶点i是否已经访问过
if (e[cur][i] == 1 && book[i] == 0)
{
//如果从顶点cur到顶点i有边，并且顶点i没有被访问过，则将顶点i入队
que[tail] = i;
tail++;
book[i] = 1; //标记顶点i已访问
}
//如果tail大于n，则表明所有顶点都已经被访问过
if(book[y]) break;//当y城市进入队列时，这时结束就行了

if (tail > n)
break;
}

}

cout<<min<<endl;

return 0;
}


#### 答案给出的代码:

#include<iostream>
using namespace std;
struct note
{
int x; //城市编号
int s; //转机次数
};

int main()
{
struct note que[2501];
int e[51][51] = { 0 }, book[51] = { 0 };
int n, m, a, b, cur, start, end, flag = 0;
cin >> n >> m >> start >> end;

//初始化二维矩阵
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (i == j) e[i][j] = 0;
else e[i][j] = 99999999;

//读入城市之间的航班
for (int i = 1; i <= m; ++i)
{
cin >> a >> b;
//注意这里是无向图
e[a][b] = 1;
e[a][b] = 1;
}

//队列初始化
tail = 1;

//从start号城市出发，将start号城市加入队列
que[tail].x = start;
que[tail].s = 0;
tail++;
book[1] = start; //标记start号城市已在队列中

//当队列不为空的时候循环
{
for (int j = 1; j <= n; ++j) //从1~n依次尝试
{
if (e[cur][j] != 99999999 && book[j] == 0)
{
//如果从城市cur到城市j有航班并且城市j不在队列中，则将j号城市入队
que[tail].x = j;
que[tail].s = que[head].s + 1; //转机次数+1
tail++;
//标记城市j己经在队列中
book[j]=1;
}
//如果到达目标城市,停止扩展,任务结束,退出循环
if (que[tail].x == end)
{
//注意下面两句话的位置千万不要写颠倒了
flag = 1;
break;
}
}
if (flag)
break;
}

//打印队列中末尾最后一个(目标城市)的转机次数
//注意tai1是指向队列队尾(即最后一位)的下一个位置，所以这需要 - 1
cout << que[tail-1].s;

return 0;
}


当然也可以使用深度优先搜索解决，但是这里用广度优先搜索会更快

**广度优先搜索更加适用于所有边的权值相同的情况**

## 五、最短路径

### 5.1 只有五行的算法———Floyd-Warshall

#### 代码:

#include<iostream>
using namespace std;
int main()
{
int e[10][10], n, m, t1, t2, t3;
int inf = 99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值
//读入n和m，n表示顶点个数，m表示边的条数
cin >> n >> m;

//初始化
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (i == j) e[i][j] = 0;
else e[i][j] = inf;

//读入边
for (int i = 1; i <= m; ++i)
{
cin >> t1 >> t2 >> t3;
e[t1][t2] = t3;
}

//Floyd-Warshall算法核心语句
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (e[i][j] > e[i][k] + e[k][j])
e[i][j] = e[i][k] + e[k][j];

//输出最终结果
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
cout << e[i][j]<<" ";
cout << endl;
}

return 0;
}


#### 总结:

• 通过这种方法我们可以求出任意两个点之间的最短路径。它的时间复杂度是O($N^3$);
• 如果时间复杂度要求不高，使用Floyd-Warshall来求指定两点之间的最短路径或者指定一个点到其余各个顶点的最短路径也是可行的。当然也有更快的算法(例如:Dijkstra算法);
• Floyd-Warshall算法不能解决带有“负权回路”(或者叫“负权环”)的图;

### 5.2 Dijkstra算法—通过边实现松弛

#### 思路:

• 将所有的顶点分为两部分:已知最短路程的顶点集合Р和未知最短路径的顶点集合Q。最开始,已知最短路径的顶点集合P中只有源点一个顶点。我们这里用一个book数组来记录哪些点在集合P中。例如对于某个顶点i，如果book[i]为1则表示这个顶点在集合P中，如果book[i]为0则表示这个顶点在集合Q中。
• 设置源点s到自己的最短路径为О即dis[s]=0。若存在有源点能直接到达的顶点i,则把dis[]设为e[s][i]。同时把所有其他(源点不能直接到达的)顶点的最短路径设为正无穷。
• 在集合Q的所有顶点中选择一个离源点s最近的顶点u(即dis[u]最小)加入到集合P。并考察所有以点u为起点的边，对每一条边进行松弛操作。例如存在一条从u到v的边，那么可以通过将边u→v添加到尾部来拓展一条从s到v的路径，这条路径的长度是 dis[u]+e[u][v]。如果这个值比目前已知的 dis[v]的值要小，我们可以用新值来替代当前dis[v]中的值。
• 重复第3步，如果集合Q为空，算法结束。最终dis数组中的值就是源点到所有顶点的最短路径。

#### 完整的Dijkstra算法代码如下:

#include<iostream>
using namespace std;
int main()
{
int e[10][10], dis[10], book[10], u, n, m, t1, t2, t3, min;
int inf = 99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值
//读入n和m，n表示顶点个数，m表示边的条数
cin >> n >> m;

//初始化
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (i == j) e[i][j] = 0;
else e[i][j] = inf;

//读入边
for (int i = 1; i <= m; ++i)
{
cin >> t1 >> t2 >> t3;
e[t1][t2] = t3;
}

//初始化dis数组，这里是1号顶点到其余各个顶点的初始路程
for (int i = 1; i <= n; ++i)
dis[i] = e[1][i];

//book数组初始化
for (int i = 1; i <= n; ++i)
book[i] = 0;
book[1] = 1;

//Dijkstra算法核心语句
for (int i = 1; i <= n - 1; ++i)
{
//找到离1号顶点最近的顶点
min = inf;
for (int j = 1; j <= n; ++j)
if (book[j] == 0 && dis[j] < min)
{
min = dis[j];
u = j;
}
book[u] = 1;
for (int v = 1; v <= n; ++v)
if (e[u][v] < inf)
if (dis[v] > dis[u] + e[u][v])
dis[v] = dis[u] + e[u][v];

}

//输出最终结果
for (int i = 1; i <= n; ++i)
cout << dis[i] << " ";
return 0;
}


#### 优化:

##### 下面来讲一下邻接表:

4 5
1 4 9
2 4 6
1 2 5
4 3 8
1 3 7


int n, m, i;
//u、v和w的数组大小要根据实际情况来设置，要比m的最大值要大1
int u[6], v[6], w[6];
//first和next的数组大小要根据实际情况来设置，要比n的最大值要大1
int first[5], next[5];
cin >> n >> m;
//初始化first数组下标1~n的值为-1，表示1~n顶点暂时都没有边
for (int i = 1; i <= n; ++i)
first[i] = 1;
for (int i = 1; i <= m; ++i)
{
cin >> u[i] >> v[i] >> w[i]; // 读入每一条边
//下面两句是关键了
next[i] = first[u[i]];
first[u[i]] = i;
}

• 这里为大家介绍的是使用数组来实现邻接表，而没有使用真正的指针链表，这是一种在实际应用中非常容易实现的方法.
• 这种方法为每个顶点i (i从1~n）都设置了一个链表,里面保存了从顶点i出发的所有的边(这里用first和next数组来实现)
• 首先我们需要为每一条边进行1~m的编号。用u、v和w三个数组来记录每条边的信息，即u[i]、v[i]和w[i]表示第i条边是从第u[i]号顶点到v[i]号顶点(u[i]→v[i])，且权值为w[i]。
• first数组的1~n号单元格分别用来存储1~n号顶点的第一条边的编号,初始的时候因为没有边加入所以都是-1。即first[u[i]保存顶点u[i]的第一条边的编号，next[i]存储“编号为i的边”的“下一条边”的编号。

#### 总结:

4个月前
class Solution {
public:
string replaceSpaces(string &str) {
string s;
for(int i=0;i<str.size();++i)
if(str[i]!=' ') s+=str[i];
else s+="%20";

return s;
}
};


4个月前
class Solution {
public:
int Fibonacci(int n) {
int num[40]={0,1};

for(int i=2;i<=n;++i)
num[i]=num[i-1]+num[i-2];

return num[n];
}
};

class Solution {
public:
int Fibonacci(int n) {
int a=0,b=1;
while(n--)
{
int c=a+b;
a=b,b=c;
}
return a;
}
};

//递归:
class Solution {
public:
int Fibonacci(int n) {
if(n<=1) return n;
return Fibonacci(n-1)+Fibonacci(n-2);

}
};